用 TOC 中的例子解释语言的正式定义？

可以从起始符号导出的所有字符串（通过终结符号）的集合是由语法 G 生成的语言。

示例 1

令文法 G 由终结符集 T = {a, b}、唯一的非终结符起始符号 S 和产生式规则集定义。因此，语法 G 将如下 -

S → ∧, S → aSb

或者简而言之，如下所述 -

S → ∧ | 锑

L(G)= {∧, ab, aabb, aaabbb, . . . }

定义

如果 G 被称为具有起始符号 S 和终结符集 T 的文法，则 G 生成的语言是以下集合 -

S → ∧ | 锑

L(G)= {s | s ∈ T* 和 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, abbabb, ababac, abababb, . . .

以下描述是否正确？

'来自 L 的任何字符串都包含 a、b（以任何顺序）并以 b 或 ac 结尾'

. . . 不！，

例如ba,abaabac∈/L

示例 3

设 ∑ = {a, b, c} 是终结符的集合，S 是唯一的非终结符。以下四个产生式描述了哪种语言？

S → ∧

S → aS

S → bS

S → cS

或者简写为 − S → ∧ | | | 乙| CS。

尝试意识到 ∑* 中的所有字符串都可以通过这些规则生成，并针对字符串 aacb 进行验证。

S ⇒ aS ⇒ aaS ⇒ aacS ⇒ aacbS ⇒ aacb∧ = aacb

因此，S⇒*aacb。