由文法生成的语言

---

---

可以从文法推导出的所有字符串的集合被称为由该文法生成的语言。由文法G生成的语言是正式定义的子集

L(G)={W|W ∈ ∑*, S ⇒G W}

如果L(G1) = L(G2)，则文法G1等价于文法G2。

示例

如果有一个文法

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

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

L(G) = {ab}

示例

假设我们有以下文法 -

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

由该文法生成的语言 -

L(G) = {ab, a²b, ab², a²b², ………}

= {a^m bⁿ | m ≥ 1 and n ≥ 1}

生成语言的文法构造

我们将考虑一些语言并将其转换为生成这些语言的文法 G。

示例

问题 - 假设，L (G) = {a^m bⁿ | m ≥ 0 and n > 0}。我们必须找出产生L(G)的文法G。

解决方案

由于 L(G) = {a^m bⁿ | m ≥ 0 and n > 0}

接受的字符串集可以重写为 -

L(G) = {b, ab,bb, aab, abb, …….}

这里，起始符号必须至少包含一个以任意数量的 'a'（包括空）开头的 'b'。

为了接受字符串集 {b, ab, bb, aab, abb, …….}, 我们采用了以下产生式 -

S → aS , S → B, B → b and B → bB

S → B → b (接受)

S → B → bB → bb (接受)

S → aS → aB → ab (接受)

S → aS → aaS → aaB → aab(接受)

S → aS → aB → abB → abb (接受)

因此，我们可以证明 L(G) 中的每个字符串都被产生的语言接受。

因此，文法 -

G: ({S, A, B}, {a, b}, S, { S → aS | B , B → b | bB })

示例

问题 - 假设，L (G) = {a^m bⁿ | m > 0 and n ≥ 0}。我们必须找出产生 L(G) 的文法 G。

解决方案 -

由于 L(G) = {a^m bⁿ | m > 0 and n ≥ 0}，接受的字符串集可以重写为 -

L(G) = {a, aa, ab, aaa, aab ,abb, …….}

这里，起始符号必须至少包含一个 'a'，后面可以跟任意数量的 'b'（包括空）。

为了接受字符串集 {a, aa, ab, aaa, aab, abb, …….}, 我们采用了以下产生式 -

S → aA, A → aA , A → B, B → bB ,B → λ

S → aA → aB → aλ → a (接受)

S → aA → aaA → aaB → aaλ → aa (接受)

S → aA → aB → abB → abλ → ab (接受)

S → aA → aaA → aaaA → aaaB → aaaλ → aaa (接受)

S → aA → aaA → aaB → aabB → aabλ → aab (接受)

S → aA → aB → abB → abbB → abbλ → abb (接受)

因此，我们可以证明 L(G) 中的每个字符串都被产生的语言接受。

因此，文法 -

G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB })