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.

Example

如果存在一个语法

If there is a grammar

G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}

此处 S 产生 AB ,我们可以用 a 替换 A ,用 b 替换 B 。这里,唯一可接受的字符串是 ab ,即

Here S produces AB, and we can replace A by a, and B by b. Here, the only accepted string is ab, i.e.,

L(G) = {ab}

Example

假设我们有以下语法 −

Suppose we have the following grammar −

G:N = {S、A、B} T = {a、b} P = {S → AB,A → aA|a,B → bB|b}

G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA|a, B → bB|b}

此语法生成的语言 −

The language generated by this grammar −

L(G) = {ab、a2b、ab2、a2b2、………}

L(G) = {ab, a2b, ab2, a2b2, ………}

{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 })