解释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。

更新于：2021年6月15日

1K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告