Problem − 假设，L (G) = {am bn | m ≥ 0 且 n > 0}。我们必须找出生成 L(G) 的语法 G 。

Solution

由于 L(G) = {am bn | 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 })

Problem − 假设，L (G) = {am bn | m > 0 和 n ≥ 0}。我们必须找出生成 L(G) 的语法 G。

Solution −

因为 L(G) = {am bn | 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 })