Automata Theory 简明教程
Language Generated by a Grammar
从语法中可以派生的所有字符串的集合称为从该语法生成的语言。语法 G 生成的语言是形式上由以下子集定义的
The set of all strings that can be derived from a grammar is said to be the language generated from that grammar. A language generated by a grammar G is a subset formally defined by
L(G)={W|W ∈ ∑ , S ⇒G *W }
L(G)={W|W ∈ ∑, S ⇒G *W}
如果 L(G1) = L(G2) ,语法 G1 等价于语法 G2 。
If L(G1) = L(G2), the Grammar G1 is equivalent to the Grammar G2.
{am bn | m ≥ 1 and n ≥ 1}
Construction of a Grammar Generating a Language
我们将考虑一些语言,并将其转换为生成那些语言的语法 G。
We’ll consider some languages and convert it into a grammar G which produces those languages.
Example
Problem − 假设,L (G) = {am bn | m ≥ 0 且 n > 0}。我们必须找出生成 L(G) 的语法 G 。
Problem − Suppose, L (G) = {am bn | m ≥ 0 and n > 0}. We have to find out the grammar G which produces L(G).
Solution
Solution
由于 L(G) = {am bn | m ≥ 0 且 n > 0}
Since L(G) = {am bn | m ≥ 0 and n > 0}
可以将可接受字符串集重写为 −
the set of strings accepted can be rewritten as −
L(G) = {b、ab、bb、aab、abb、…….}
L(G) = {b, ab,bb, aab, abb, …….}
这里,起始符号必须至少带有一个“b”,前面可以有任意数量的“a”,包括空串。
Here, the start symbol has to take at least one ‘b’ preceded by any number of ‘a’ including null.
为了接受字符串集 {b、ab、bb、aab、abb、……},我们采用了以下产生式 −
To accept the string set {b, ab, bb, aab, abb, …….}, we have taken the productions −
S → aS,S → B,B → b 且 B → bB
S → aS , S → B, B → b and B → bB
S → B → b(已接受)
S → B → b (Accepted)
S → B → bB → bb(已接受)
S → B → bB → bb (Accepted)
S → aS → aB → ab(已接受)
S → aS → aB → ab (Accepted)
S → aS → aaS → aaB → aab(已接受)
S → aS → aaS → aaB → aab(Accepted)
S → aS → aB → abB → abb(已接受)
S → aS → aB → abB → abb (Accepted)
因此,我们可以证明 L(G) 中的每个字符串都由生成集合所生成的语义接受。
Thus, we can prove every single string in L(G) is accepted by the language generated by the production set.
因此语法 −
Hence the grammar −
G: ({S, A, B}, {a, b}, S, {S → aS | B , B → b | bB })
G: ({S, A, B}, {a, b}, S, { S → aS | B , B → b | bB })
Example
Problem − 假设,L (G) = {am bn | m > 0 和 n ≥ 0}。我们必须找出生成 L(G) 的语法 G。
Problem − Suppose, L (G) = {am bn | m > 0 and n ≥ 0}. We have to find out the grammar G which produces L(G).
Solution −
Solution −
因为 L(G) = {am bn | m > 0 和 n ≥ 0},可接受的字符串集可重新写为 −
Since L(G) = {am bn | m > 0 and n ≥ 0}, the set of strings accepted can be rewritten as −
L(G) = {a, aa, ab, aaa, aab ,abb, …….}
此处,起始符号必须至少取一个“a”,后跟任意数量的“b”,包括零。
Here, the start symbol has to take at least one ‘a’ followed by any number of ‘b’ including null.
为接受字符串集 {a, aa, ab, aaa, aab, abb, …….}, 我们取了下面这些生成 −
To accept the string set {a, aa, ab, aaa, aab, abb, …….}, we have taken the productions −
S → aA, A → aA , A → B, B → bB ,B → λ
S → aA → aB → aλ → a (接受)
S → aA → aB → aλ → a (Accepted)
S → aA → aaA → aaB → aaλ → aa (接受)
S → aA → aaA → aaB → aaλ → aa (Accepted)
S → aA → aB → abB → abλ → ab (接受)
S → aA → aB → abB → abλ → ab (Accepted)
S → aA → aaA → aaaA → aaaB → aaaλ → aaa (接受)
S → aA → aaA → aaaA → aaaB → aaaλ → aaa (Accepted)
S → aA → aaA → aaB → aabB → aabλ → aab (接受)
S → aA → aaA → aaB → aabB → aabλ → aab (Accepted)
S → aA → aB → abB → abbB → abbλ → abb (接受)
S → aA → aB → abB → abbB → abbλ → abb (Accepted)
因此,我们可以证明 L(G) 中的每个字符串都由生成集合所生成的语义接受。
Thus, we can prove every single string in L(G) is accepted by the language generated by the production set.
因此语法 −
Hence the grammar −
G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB })