由文法生成的語言

---

---

可以從文法推匯出的所有字串的集合被稱為由該文法生成的語言。由文法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 })