正则语言

阐述

能被某个有限自动机识别的语言。

定理

正则语言的集合对交集、并集、连接、星号、补集、取反封闭。

泵引理

如果 $A$ 是正则语言，那么存在一个数 $p$，对于任何 $|s|\ge p$，都有 $s=xyz$，并且

• $xy^iz\in A$ 对于每个 $i\ge0$
• $|y|>0$
• $|xy|\le p$

证明：这里的 $p$ 实际对应于 DFA 的状态数量。

实例

性质

相关内容

CFL

参考文献