编译原理 有限自动机

有限自动机是对语言有穷描述的一种方法，下面将介绍确定有限自动机、非确定有限自动机和他们之间的转化以及确定有限自动机的最小化。

确定有限自动机

确定有限状态自动机 A 是由

1. 一个非空有限的状态集合 Q
2. 一个输入字母表（非空有限的字符集合）
3. 一个转移函数
4. 唯一开始状态
5. 一个接受状态的集合 (终止状态集合)

组成的五元组。

转换函数

f(0,a) = 1

处于状态 0 时输入字符状态迁移为 1

转换矩阵

状态为 0 时输入字符 a 状态迁移为 1

状态为 1 时输入字符 a 状态迁移为 3

状态转换图

从起点状态 1 开始，如果输入字符 0 或 1 状态迁移为 2；在状态 2 输入字符 1 时状态转移为 3。

两个圆圈的为终止状态。

非确定有限自动机

在确定有限自动状态机上稍加修改，使其在某状态下输入一个字符的转换状态不是唯一的，而允许转换为多个状态，并允许不扫描字符就可以转换状态。

非确定有限状态自动机 A 是由

1. 一个非空有限的状态集合 Q
2. 一个输入字母表（非空有限的字符集合）
3. 转移函数
4. 开始状态集合
5. 一个接受状态的集合 (终止状态集合)

组成的五元组。

与确定有限状态机区别

1. 状态转换函数是一个子集，一个状态结点出发可以有不止一条同一标记的弧
2. 不处理任何符号就可以转换
3. 初态不止一个
4. DFA 是 NFA 的特例

转换函数

f(0,a) = {0, 1, 2, 3}

处于状态 0 时输入字符状态迁移为 0，1，2，3

转换矩阵

状态为 0 时输入字符 a 状态迁移为 1，2

状态为 1 时输入字符 a 状态迁移为 3，4

NFA 转 DFA

对于任何一个 NFA，都存在一个 DFA，使其等价。

思路

根据 NFA 和 DFA 的不同构造 DFA

消除初始状态不同

引进初态结点 X 和终态结点 Y，从 X 到原来的初态各连接一条ε弧，从原所有来终态各引出一条ε弧到终态 Y。现在只有一个唯一的初态，唯一的终态。

状态替换

1. i–AB–>j 代之为 i–A–k–B–>j。引入新状态 k

子集法

ε-闭包

I 是状态集的一个子集，I 的ε-闭包为：

ε-closure(I) = I∪{s1 | 从某个 s∈I 出发经过任意条ε弧能达到 S1}

设 a 是字符集中一个字符，定义

$$I_a = ε-closure(J)$$

其中，J 为 I 中的某个状态出发经过一条 a 弧而到达的状态集合。也就是说经过任意 (0-n) 个ε弧到 a 再经过任意 (0-n) 个ε弧到达的状态的集合就是 I_a。

例题

要求 I_a，则要求 J，J = {5，4，3}

I_a = ε-closure(J) = {5,4,3,6,2,7,8}

确定化

不失一般性，设字母表只含两个字符 a、b，构造计算状态集的转化表

1. 置第一行第一列为ε-closure(X)，求这一列的 I_a,I_b
2. 检查这两个 I_a,I_b 是否在表中出现过，把没有出现的在填在空行的第一列。
3. 直到所有的 I_a,I_b 全部出现过。