跳到主要内容

正则语言

阐述

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

定理

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

泵引理

如果 AA 是正则语言,那么存在一个数 pp,对于任何 sp|s|\ge p,都有 s=xyzs=xyz,并且

  • xyizAxy^iz\in A 对于每个 i0i\ge0
  • y>0|y|>0
  • xyp|xy|\le p

证明:这里的 pp 实际对应于 DFA 的状态数量。

实例

性质

相关内容

CFL

参考文献