复习
有限自动机分为两种：不确定的有限自动机（NFA）和确定的有限自动机（DFA）。我们分别用一个五元组表示。不确定的有限自动机：
- 有限状态集合S.
- 输入符号集合Σ
- 转换函数move:Sx(Σ∪(ε)->p(s))
- 状态S0是唯一的开始状态
- 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算法的分析
自顶向下算法
规则如下：
1.AB
添加一个状态
2.A|B
添加两条边，不添加空串和状态
3.A*
添加三条边、两个空串
自顶向下算法分析
和MYT算法同样，分块构建NFA。区别在于比较简单，引入空串、新边较少，之后化简就会容易。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/14570.html