数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在TOC中解释语言的正式定义并举例说明。
由文法G生成的语言是由起始符号可以导出的所有字符串（在终结符上）的集合。
示例1
设文法G由终结符集T = {a, b}、唯一的非终结符起始符号S和产生式规则集定义。因此，文法G如下所示：
S → ∧, S → aSb
或者简写为：
S → ∧ | aSb
L(G) = {∧, ab, aabb, aaabbb, . . . }
定义
如果G被称为具有起始符号S和终结符集T的文法，则G生成的语言是以下集合：
S → ∧ | aSb
L(G) = {s | s ∈ T* and S ⇒+ s}.
也就是说，它是所有仅包含终结符的字符串的集合，这些字符串可以使用一个或多个步骤从起始符号导出。
示例2
设∑ = {a, b, c}为终结符集，{A, S}为非终结符集，起始符号为S。∑上的语言L由以下产生式定义：
S → b | aA, A → c | bS
属于语言L的字符串示例如下：
显然，我们可以生成b。所有较长的字符串都以a开头。所有字符串都以b或ac结尾。
我们可以生成字符串：b, ac, abb, abac, ababb, ababac, abababb, . . .
以下特征描述是否正确？
“L中的任何字符串都包含a、b（任意顺序），并以b或ac结尾”
… 不！
例如，ba, abaabac ∉ L
示例3
设∑ = {a, b, c}为终结符集，S是唯一的非终结符。以下四个产生式描述的是什么语言？
S → ∧
S → aS
S → bS
S → cS
或者简写为：S → ∧ | aS | bS | cS。
尝试理解这些规则可以生成∑*中的所有字符串，并验证字符串aacb。
S ⇒ aS ⇒ aaS ⇒ aacS ⇒ aacbS ⇒ aacb∧ = aacb
因此，S ⇒*aacb。
更新于：2021年6月15日
3K+ 次浏览
广告