基于MYT算法和自顶向下算法从正则表达式到NFA

算法和自顶向下算法从正则表达式到NFA"/>

基于MYT算法和自顶向下算法从正则表达式到NFA

复习

有限自动机分为两种：不确定的有限自动机（NFA）和确定的有限自动机（DFA）。我们分别用一个五元组表示。不确定的有限自动机：

1. 有限状态集合S.
2. 输入符号集合Σ
3. 转换函数move:Sx(Σ∪(ε)->p(s))
4. 状态S₀是唯一的开始状态
5. F包含于S是接受状态集合

确定的有限状态自动机1、2、4、5与NFA一样。转换函数move:Sx(Σ)->p(s)，两者区别在于：有限自动机任何状态下没有ε转换，一个符号标记离开同一状态只有一条边。

MYT算法

规则如下：

1.st

不添加空串，添加一个状态
2.一个字符（可以是空字符）
添加一条边，一个状态

3.s|t

添加四个空串，四个状态

4.s^*添加四个空串、四条边、四个状态（图下面一条i到f的边被遮住了）

一些似乎不是很重要的性质：

• N(s)的状态数最多是s的状态数的两倍。
• N(s)的每一个状态有一个用Σ里的符号标记的指向其他节点的转换或者最多两个指向其他节点的ε转换。

MYT算法的分析

为了应付考试，我们可以说会手工建NFA就行。比较迅速的方法就是从嵌套多的地方入手，像搭积木一样搭建NFA。为了避免出错，建议时刻记住每个转换的添加的边数和空串数。
MYT算法的好处在于，任何字符串都能通过这个算法转换成NFA，它是沿着正则表达式的语法分析树自底向上递归处理的。不过我们可以发现，要添加的空串和边实在是太多了，这为我们后面继续转换成DFA带来了很多不少麻烦，因此这也是有代价的。

自顶向下算法

规则如下：

1.AB
添加一个状态
2.A|B
添加两条边，不添加空串和状态
3.A^*
添加三条边、两个空串

自顶向下算法分析

和MYT算法同样，分块构建NFA。区别在于比较简单，引入空串、新边较少，之后化简就会容易。