由语法生成的语言

---

可以从语法派生的所有字符串的集合被称为从该语法生成​​的语言。由文法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 且 n ≥ 1}

构建语法生成语言

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

例子

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

解决方案

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

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

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

这里，起始符号必须至少有一个“b”，前面有任意数量的“a”，包括空值。

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

S → aS 、S → B、B → b 和 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 且 n ≥ 0}。我们必须找出产生 L(G) 的文法 G。

解决方案-

由于 L(G) = {a ^m b ⁿ | m > 0 且 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 })