解釋2型文法及其性質

2型文法是上下文無關文法 (CFG)。

所有產生式都具有以下形式：

A → x — 其中A是非終結符，x是非終結符和終結符的字串。

上下文無關文法等價於下推自動機 (PDA) 和上下文無關語言。

示例 — 下推自動機 (PDA)

性質

• 如果產生式規則的形式為A → α，則稱文法G = (V, T, P, S)為上下文無關文法。

• 轉換允許A → ε [即，α → ε]，其中A是非終結符，α是任何終結符或非終結符。

• 這裡，轉換規則的左側只包含一個非終結符。

• 2型文法是大多數程式語言（如XML）語法基礎。性質

CFG在以下方面是封閉的：

• 並集

• 連線

• 克林閉包

它在補集、替換和逆轉方面不是封閉的。

示例

考慮產生式P ⇒ {S → aSa, S → bSb, S → ε}

Since S → aSa
   → aaSaa [as S → aSa]
   → aabSbaa [as S → bSb]
   → aabbaa [as S → ε]

因此，S可以生成S = {ε, aa, bb, abba, aabbaa, abaaba, …}

因此，該語言定義為L(G) = {w wR | w ε {a, b}*}

可以使用使用堆疊記憶體儲存符號的下推自動機來處理CFG。

Bhanu Priya

更新於：2021年6月15日

1K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習