- snjk
-
从正规式开始
通过下面的对应法则将正规式转换成NFA
例如:
运用子集法的3个概念:
(1 )状态集的ε-闭包: 状态集I中的任何状态s经任意条ε弧而能到达的所有状态的集合,定义为状态集I的ε -闭包,表示为ε -closure()。
(2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合,定义为状态集1的a弧转换,表示为move(l,a)。
(3)状态集的a弧转换的闭包a: lg= ε-closure(move(l,a))
上面的正规式转换成NFA:
先从初态0开始求:
u2003u2003【因为每个状态通过一条ε弧到达自己本身,所以求得ε的闭包包含自己】
(1)求0的ε的闭包:经过任意条ε所能到达的状态,集合为{0,1,3,4,5,6,7,9}
(2)求0的a弧转换:1经过a弧到达2,4经过a弧到达4,其余没有经过一条a弧到达某个状态,所以集合为{2,4}
(3)求a弧转换的闭包:{2,4}分别经过任意条ε所能到达的状态,集合为{2,4,6,7,9}
(4)求0的b弧转换:5经过b到5,7经过b到8,,其余没有经过一条b弧到达某个状态,所以集合为{5,8}
(5)求b弧转换的闭包:{5,8}分别经过任意条ε所能到达的状态,集合为{5,6,7,8,9}
0的ε-闭包:{0,1,3,4,5,6,7,9}
0的a弧转换:{2,4}
0的a弧转换的ε-闭包:{2,4,6,7,9}
0的b弧转换:{5,8}
0的b弧转换的ε-闭包:{5,6,7,8,9}
现在列一个表格:
(1)表格的列数为输入字符的个数+1,此题为a,b两个输入字符,所以为3列。
(2)第一列第一行填写初态的ε-闭包(此题0的ε-闭包),第二列第一行填写初态的a弧转换的ε-闭包(此题0的a弧转换的ε-闭包),第三列第一行填写初态的b弧转换的ε-闭包(此题0的b弧转换的ε-闭包)......以此类推。
(3)第一列的第二行以下填入上一行第二列以后的没有出现过的状态集。(此题第一行第二列第三列都没有出现在第一列中,将他们填入第一列)
下图为填好的表:
【新的终态的判断方法就是包含原来终态的集合就为终态,例如此题原来终态为9,所以包含9的集合就为终态,[双圈代表终态];
新的初态就是包含原来初态的集合就为初态,例如此题原来初态为0,所以包含0的集合就为初态】
为表里的状态集重新标上号:
先了解几个概念:
1.多于状态:对于一个状态Si,若从开始状态出发,不可能到达改状态Si,则Si为多余(无用)状态。
2.死状态:对于一个状态Si,对于任意输入符号a,若转到它本身后,不可能从它到达终止状态,则称Si为死状态。
都称为无关状态
3.等价状态:若Si为自动机的一个状态,我们把从Si出发能导出的所有符号串的集合记为L(Si)。
设有两个状态Si和Sj,若有L(Si)=L(Sj),则称Si和Sj是等价状态。
4.可区别状态:自动机中两个状态Si和Sj,如果它们不等价,则称它们可区别。
5.两个状态(Si和Sj)等价的判断条件:
(1)状态Si和Sj必须同时为终止状态或同时为非终止状态。即终止状态和非终止状态是可区别的。
(2)状态Si和Sj对于任意输入符a∈Σ,必须转到等价的状态里,否则Si和Sj是可区别的。
DFA的化简算法:对于DFA M=(S,Σ,f,S0,Z)
(1)首先将DFA的状态集进行初始化,分成Π=(Z,S-Z);
(2) 用下面的过程对Π构造新的划分Π new
for (Π中每个组G) do //每个组都是一个状态集
begin
把G划分成小组,G中的任意两个状态Si和Sj在同一组中,当且仅当对于Σ中任意输入符号a ,Si和Sj的a转换是到同一组中,move(Si,a) ∈Gi ,move(Sj,a) ∈Gi。这样,只要Si和Sj的a转换是到不同的组中,则说明Si和Sj是可区别的,可进行划分。在Π new中用刚完成的对G的划分代替原来的G。
end ; Π := Π new;
(3)重复执行(2),直到Π中每个状态集不能再划分(Π new= Π)为止;
(4)合并等价状态 ,在每个G中,取任意状态作为代表,删去其它状态;
(5)删去无关状态,从其它状态到无关状态的转换都成为无定义。
举例:
之前上面这个图画错了,现在图已经修改过了,谢谢提醒 :-D