Lec 14 : Computation Theory NFSA with empty move into NFSA
without empty move
1
Convert NFSA with empty move into NFSA without empty move
if there is NFSA with empty move M=(Q, ?,q0,t,F) then there isSA without empty move M-=(Q-,?,q0,t-,F-)
Define t : Q×( ??{?} ) ? Q
By
t(K,?)=R(K) or ?-closure(K)
t(K,a)=R(t(R(K),a))
The set of final states F- is F ?{q}if R(q) ?F
Example : convert the NFSA with empty move into without empty move
t(q0,0)=R(t(R(q0),0))=R(t({q0,q1,q2},0))={q0,q1,q2}
t(q0,1)=R(t(R(q0),1))= R(t({q0,q1,q2},1))={q1,q2}
t(q0,2)= R(t(R(q0),2))= R(t({q0,q1,q2},2))={q2}
t(q1,0)=R(t(R(q1),0))=R(t({q1,q2},0))={}
t(q1,1)=R(t(R(q1),1))= R(t({q1,q2},1))={q1,q2}
?
?
0
1
2
q0
q2
q1
Lec 14 : Computation Theory NFSA with empty move into NFSA
without empty move
2
t(q1,2)= R(t(R(q1),2))= R(t({q1,q2},2))={q2}
t(q2,0)=R(t(R(q2),0))=R(t({q2},0))={}
t(q2,1)=R(t(R(q2),1))= R(t({q2},1))={}
t(q2,2)= R(t(R(q2),2))= R(t({q2},2))={q2}
F-={q0,q1,q2}
0
0,1
0,1,2
1
1,2
2
q0
q2
q1