由语法生成的语言
可以从语法中派生出的所有字符串的集合被称为由该语法生成的语言。由语法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, a2b, ab2, a2b2, ………
= {am bn | m ≥ 1 and n ≥ 1
构造生成语言的语法
我们将考虑一些语言并将其转换为生成这些语言的语法 G。
示例
问题 −假设 L (G) = {am bn | m ≥ 0 and n > 0}。我们必须找出产生 L(G) 的语法 G。
解决方案
由于 L(G) = {am bn | m ≥ 0 and n > 0
接受的字符串集合可以重写为 −
L(G) = {b, ab,bb, aab, abb, …….
这里，起始符号必须至少有一个'b'，前面有任意数量的'a'，包括 null。
要接受字符串集合 {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) = {am bn | m > 0 和 n ≥ 0}。我们必须找出产生 L(G) 的语法 G。
解决方案 −
由于 L(G) = {am bn | m > 0 和 n ≥ 0}，则接受的字符串集合可以重写为 −
L(G) = {a, aa, ab, aaa, aab ,abb, …….>
此处，起始符号必须至少有一个'a'，后跟任意数量的'b'，包括 null。
要接受字符串集合 {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 })
