《不确定的有限状态自动机》由会员分享，可在线阅读，更多相关《不确定的有限状态自动机（195页珍藏版）》请在金锄头文库上搜索。
1、.4 不确定的有限状态自动机,每个FSL都是右线性语言 (定理3-1),问题,每个右线性语言是不是一个FSL？,例,接收语言aa，ab的FA,省略陷阱状态,q1,a,b,q0,q2,a,a,q3,该自动机识别的语言L=aa，ab 是右线性语言；但自动机不是DFA。,(q0，a)=q1，q2即没有到达确定的惟一的状态。不确定的有限状态自动机-NFA,3.4.1不确定的有限状态自动机,定义3-10 NFA是一个五元式，NFA =（Q，Q0，F） 其中：Q 是一个有限状态的集合 是字母表,Q0 Q 是开始状态集合F Q 是接收状态集合,是Q2Q的状态转换函数 即(q，a) 2QNFA在状态q，扫描字
2、母a后到达 可能的下一状态集合。,NFA与DFA,NFA有一个可能的开始状态集合和可能的下一状态集合其余的同DFA。,NFA与DFA的重要区别在于转移函数的不同。(q，x)对应的是状态的一个子集,FA处于状态q,DFA对每个字母只有一个状态的转移。 NFA对某个字母可以有多个状态转移； NFA接收该字母时,从多个状态转移中非确定地选择任意一个。,具体地,对于NFA， (q，a) Q (q，a) 有3种可能(q，a) =(q，a) =q1(q，a) =q1 ，q2，qn,或,或,(q，a)仍是一个状态转换函数，只是其值域发生了改变。所有(q，a)对应的所有子集元素个数都为1时，NFA退化为DFA
3、,NFA停机,NFA在两种情况下自动停机：将输入串扫描结束(q，a)=(即对应没有定义),或,在扫描一个串w时，NFA的状态发生转换，可能会有多种情况：可能在接收状态时终止；可能在非接收状态时终止；也可能在中途停止。,若至少存在一条路径可以使NFA在扫描串w后到达接收状态则串w能被NFA所识别。,对于字母表上的NFA，它能识别的所有串的集合，称为NFA能识别的语言。记为 L(NFA),问题,如何形式化定义L(NFA)?,定义3-11NFA扩展状态转换函数,给定NFA，扩展的状态转换函数*：2Q*2Q 为*(p，w)= Q即NFA在状态集合p时，扫描串w后到达可能的的状态集合Q。,NFA扩展状态
4、转换函数,若p= q1，q2，qn；*（p，）=p,a,*(p，a)= (q，a)|qp=(q1, a),(q2, a),(qn, a),对于串w,w=a*(p， w)=*(p，a)= (q，a)| q*(p，),或,w= a *(p， w )=*(p， a )= *(q,)| q*(p， a ),L(NFA)表示被NFA所接收的语言 L(NFA)=w|w*且*(Q0， w)F,它表示所有串w的集合在NFA的状态图中，至少存在一条路径以w为标记，能使NFA从某个开始状态到达某个接收状态。,3.4.2 NFA的确定化,DFA可以转换为NFA NFA可以转换为DFA(确定化),A的充分条件为BA的
5、必要条件为BA当且仅当B即A的充要条件为B,B=A,A=B,定理3-3,*的一个子集L是一个FSL，充要条件为存在NFA，使得L(NFA)=L。,证明：= 必要性,若L是FSL，则有L=L(DFA）DFA=(Q ， ， ， q0 ， F) 构造NFA=(Q，1，q0，F),1(q，a)=(q，a)即把DFA的一个状态 当作NFA的一个状态集合则L=L(DFA)=L(NFA),证明: 0,NFA状态转移图,q0,0,1,0,1,2,2,q1,q2,q3,或,q0,0,1,0,1,2,2,q1,q2,q3,例3-27构造NFA，识别,0，1上的语言L=0n1m2k|n,m,k=0,0,1,0,1,
6、2,2,q3,q0,q1,q2,2,1,2,或 多个开始状态的NFA,1,0,2,2,q3,q1,q2,1,2,3.5 带动作的有限状态自动机,对于FA（DFA、NFA），有(q，)=q*(q，)=q*(P，)=P,表示FA不读入任何字母(即只扫描空串时)，FA的状态不发生改变，并且读头不进行移动，仍然指向当前非空字符。,若允许FA在不读入任何字符时,FA的状态可以发生改变，则FA为带有动作的FA,定义3-14带动作的有限状态自动机,带有动作的FA是一个五元式,-FA=(Q，Q0，F)Q，Q0，F的含义同NFA,: Q 2Q(q，a) 2Q(q, ) 2Q,即,具体,(q，a)= 表示自动机在
7、读入字母a后，自动机停机。,(q,)=q表示自动机在状态q时，不读入任何字母，自动机状态不变并且读头不移动；,(q，a)=p1，p2，p3，pm 表示自动机在读入字母a后，自动机的状态可以选择地改变为p1，p2，p3，或者pm并将读头向右移动一个单元；,(q,)=q1，q2，q3，qn表示自动机在状态q时，不读入任何字母，自动机的状态可以选择地改变为q1，q2，q3，或qn并且读头不移动；,注意,带有动作的FA一定是NFA。 一般，记为-NFA。,例3-28,使用-NFA接收语言L=0*1*2*即 L=0n1m2k|n,m,k=0,状态图,0*1*2*,q0,q1,q2,2,0,1,对应的5个函数为： (q0，0)=q0 (q0，)=q1 (q1，1)=q1 (q1，)=q2 (q2，2)=q2,定义3-15,对于-NFA ，qQ从q开始，扫描1个或多个后能够到达的状态集记为-CLOSURE(q)。,-CLOSURE(q)= p|从q到p有标记全是的有 向路,对于-NFA， qQ-CLOSURE(q)是由递归规则确定的状态集：,规则,(1) q-CLOSURE(q)即任意状态q接收空串，至少都能保持状态q不变；,规则,(2) 如果p-CLOSURE(q) 则(p,) -CLOSURE(q) (3) 重复(2)，直到-CLOSURE(q)中的状态不再增加为止。,
