前置概念

  • 字母表:符号的集合,例如英文字母表、二进制字母表
  • 字符串:符号构成的有限序列,空字符串用 表示。字符串的长度用 表示。
  • 表示所有长度为 的字符串组成的集合, 表示所有字符串组成的集合。
  • 来自相同字母表的字符串可以拼接。 拼接用 表示。
  • 次方:
  • 反转:用 表示。
  • 语言:
  • 就是 中任意多个字符串拼接得到的新字符串集合。

DFA

有限自动机是一个五元组 ,其中

  • 是有限状态集
  • 是字母表
  • 是转移函数
  • 起始状态
  • 是接收状态

如果 接收的字符串组成的集合为 ,则写 ,表示 识别

IMPORTANT

判定和识别是不一样的。识别(recognize)只要求自动机接收满足要求的字符串,而对其他的没有要求;判定(decide)要求对于其他的停机并拒绝。

NFA

  • 确定型有限自动机:DFA,一个状态 + 一个字母 唯一推出下一个状态
  • 非确定型有限自动机:NFA,可能有多个下一个状态,只要有一种到达接收状态,就说它接收输入。

NFA 是一个五元组

  • 是有限状态集
  • 是字母表
  • 是转移函数,其中 的幂集
  • 起始状态
  • 是接收状态

每个 NFA 都可以转换为一个 DFA。定义这个 DFA:

  • ,其中 表示 自己或者是 经过 转移得到的状态集合

GNFA

GNFA 在 DFA 的基础上,还要求:

  • 初始状态没有入边
  • 接收状态没有出边
  • 其他状态都有到每个其他状态以及它自己的边

WARNING

虽然 GNFA 的名字,但是它跟 DFA 更像。

每个 DFA 都可以转换为一个 GNFA。转换方法:

  • 加一个新状态作为初始状态,用 连到旧的初始状态。
  • 加一个新状态作为接收状态,用 连到旧的接收状态。
  • 补充连边。

正则语言

称一个语言是正则的当且仅当有一个有限自动机识别它。这可以是 也可以是

识别正则语言的时间复杂度是 ,空间复杂度是

正则语言的并、连接、 和补操作保持正则语言。

一个语言是正则语言当且仅当它可以被正则表达式表达。

泵引理

是一个正则语言,则存在 使得对任意长度至少为 的字符串 可以拆成三部分的拼接形式 并且

TIP

可以用来反证 不是正则语言。