有限自动机是更一般化的状态转化图。分为确定有限自动机(DFA)和不确定有限自动机(NFA)。
1.确定的有限状态自动机
M =(S,∑,f,So,Z)其中:
S是一个有限状态集合。
∑是一个字母表,输入字符的集合。
f是从S x ∑*至S的子集映照。
S0⊆S,是唯一的初态。
Z⊆S,是一个终态集。
下图为一个确定的有限状态自动机
2.不确定的有限状态自动机
M =(S,∑,f,So,Z)其中:
S是一个有限状态集合。
∑是一个字母表,输入字符的集合。
f是从S x ∑*至S的子集映照。
S0⊆S,是一个非空初态集。
Z⊆S,是一个终态集。
下图为一个不确定的有限状态自动机
3.对比NFA和DFA
说了半天其实它们的本质区别就在于S0,确定的有限状态自动机的S0是唯一确定的。而不确定的有限状态自动机的初态是一个集合,即有多个初态。
4.NFA转换为DFA
就拿上面的这个NFA图来举例说明NFA向DFA的转换方法
找出NFA的初态集
找出初态集中的每一个初态分别通过0和1到达的状态
将通过b找到的集合(此集合不能同初态一样也不能为空)重新作为初态,继续b
重复b,c直到没有新的集合将得到的状态进行编号(这些状态不能重复且不包括空状态)
重新连接就是DFA了
本人认为 以上方法通过画表格的形式最容易解题了,以下是我做到d步时的表格
e步:将得到的状态进行编号
f步:将e中得到的结果连接起来得到DFA
5.为什么要将NFA转换成DFA呢?
因为NFA是一种状态不确定的自动机,所以这种自动机不便机器实现;DFA是有限确定状态的自动机,它的状态转换的条件都很确定,所以它比较方便机器实现,同时在识别能力也和NFA相当(相关的书中已经证明了每一种NFA都可转换为同样识别能力的DFA),所以转换为DFA是更利于实现的
这就是我认识的有限自动机,如果哪里有不对的地方希望各位帮忙指出,谢谢啦