上下文无关语言

阐述

由上下文无关文法生成的语言。

泵引理

如果 $A$ 是上下文无关语言，则存在 $p$，当 $|s|\ge p$ 时都有 $s=uvxyz$ 使得

• $uv^ixy^iz\in A$ for $i\ge0$
• $|vy|>0$
• $|vxy|\le p$

证明：将树的其中一部分大小进行替换。

实例

性质

相关内容

参考文献