為語言 L = {anbm| m≠n} 生成一個上下文無關文法？

上下文無關文法是一個四元組 G = (N, T, P, S)，

其中，

• N 是非終結符的有限集合，

• T 是終結符的有限集合，N ∩ T = ∅，

• P 是形如 A → α 的產生式的有限集合，

• 其中 A ∈ N，α ∈ (N ∪ T)*，

• S 是開始符號，S ∈ N。

為語言 L = {anbm| m ≠n} 構造一個上下文無關文法

情況 1

n > m - 我們生成一個具有相同數量的 a 和 b 的字串，並在左側新增額外的 a -

S → AS1, S1 → aS1b, S1 → λ, A → aA, A → a

情況 2

n < m - 我們在右側新增額外的 b -

S → S1B, B → bB, B → b.

典型推導

S ⇒ AS1 ⇒ aAS1 ⇒ aaAS1 ⇒ aaaS1 ⇒ aaaaS1b ⇒ aaaab 或

S ⇒ S1B ⇒ aS1bB ⇒ aS1bb ⇒ abb

考慮另一個關於 上下文無關文法和語言 的例子

• 每個正則文法都是上下文無關的，因此正則語言也是上下文無關的。

• 正則語言族是上下文無關語言族的一個真子集。

示例

令 G = ({S}, {a, b}, P, S)，其中

P = {S → aSa, S → bSb, S → λ}。

典型推導 - S ⇒ aSa ⇒ aaSaa ⇒ aabSbaa ⇒ aabbaa。

L(G) = {wwR | w ∈ {a, b}*}

Bhanu Priya

更新於: 2021-06-16

6K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習