انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

convert NFSA with empty move into NFSA without empty move

if there is NFSA with empty move M=(Q, ?,q₀,t,F) then there isSA without empty move M^-=(Q^-,?,q₀,t^-,F^-)

Define t: Q×(?E{e})®Q

By

t(K,e)=R(K) or e-closure(K)

t(K,a)=R(t(R(K),a))

The set of final states F^- is F E{q}if R(q) IF

ex: convert the NFSA with empty move into without empty move

t(q₀,0)=R(t(R(q₀),0))=R(t({q₀,q₁,q₂},0))={q₀,q₁,q₂}

t(q₀,1)=R(t(R(q₀),1))= R(t({q₀,q₁,q₂},1))={q₁,q₂}

t(q₀,2)= R(t(R(q₀),2))= R(t({q₀,q₁,q₂},2))={q₂}

t(q₁,0)=R(t(R(q₁),0))=R(t({q₁,q₂},0))={}

t(q₁,1)=R(t(R(q₁),1))= R(t({q₁,q₂},1))={q₁,q₂}

t(q₁,2)= R(t(R(q₁),2))= R(t({q₁,q₂},2))={q₂}

t(q₂,0)=R(t(R(q₂),0))=R(t({q₂},0))={}

t(q₂,1)=R(t(R(q₂),1))= R(t({q₂},1))={}

t(q₂,2)= R(t(R(q₂),2))= R(t({q₂},2))={q₂}

F^-={q₀,q₁,q₂}

DONE

Instructor: Mohamed U. Mahdi