前置概念
- 字母表:符号的集合,例如英文字母表、二进制字母表
- 字符串:符号构成的有限序列,空字符串用 表示。字符串的长度用 表示。
- 表示所有长度为 的字符串组成的集合, 表示所有字符串组成的集合。
- 来自相同字母表的字符串可以拼接。 和 拼接用 表示。
- 次方:。
- 反转:用 表示。
- 语言:
- 就是 中任意多个字符串拼接得到的新字符串集合。
DFA
有限自动机是一个五元组 ,其中
- 是有限状态集
- 是字母表
- 是转移函数
- 是起始状态
- 是接收状态
如果 接收的字符串组成的集合为 ,则写 ,表示 识别 。
IMPORTANT
判定和识别是不一样的。识别(recognize)只要求自动机接收满足要求的字符串,而对其他的没有要求;判定(decide)要求对于其他的停机并拒绝。
NFA
- 确定型有限自动机:DFA,一个状态 + 一个字母 唯一推出下一个状态
- 非确定型有限自动机:NFA,可能有多个下一个状态,只要有一种到达接收状态,就说它接收输入。
NFA 是一个五元组
- 是有限状态集
- 是字母表
- 是转移函数,其中 是 的幂集
- 是起始状态
- 是接收状态
每个 NFA 都可以转换为一个 DFA。定义这个 DFA:
- ,其中 表示 自己或者是 经过 转移得到的状态集合
GNFA
GNFA 在 DFA 的基础上,还要求:
- 初始状态没有入边
- 接收状态没有出边
- 其他状态都有到每个其他状态以及它自己的边
WARNING
虽然 GNFA 的名字,但是它跟 DFA 更像。
每个 DFA 都可以转换为一个 GNFA。转换方法:
- 加一个新状态作为初始状态,用 连到旧的初始状态。
- 加一个新状态作为接收状态,用 连到旧的接收状态。
- 补充连边。
正则语言
称一个语言是正则的当且仅当有一个有限自动机识别它。这可以是 也可以是 。
识别正则语言的时间复杂度是 ,空间复杂度是 。
正则语言的并、连接、 和补操作保持正则语言。
一个语言是正则语言当且仅当它可以被正则表达式表达。
泵引理
若 是一个正则语言,则存在 使得对任意长度至少为 的字符串 , 可以拆成三部分的拼接形式 并且
TIP
可以用来反证 不是正则语言。