Sunday, March 24, 2019
Home > Theory Of Computation > Conversion Of E-NFA To NFA – Finite Automata –

Conversion Of E-NFA To NFA – Finite Automata –

Conversion Of E-NFA To NFA – Finite Automata

The Process Of Conversion Of ε-NFA To NFA Is Called As Thomson Construction.

Note:-

  1. No Change In Initial State
  2. No Change In The Total No. Of States
  3. May Be Change In Final States

Algorithm

Let M=(Q,Σ,δ,q0,F) – ε-NFA

M1= (Q1,Σ,δ1,q01,F1) – NFA

1) Initial State

q01=q0

2) Construction Of δ1

δ1

(q,x)=ε-Closure(δ(ε-Closure(q),x)

3) Final State

Every State Who’s ε-Closure Contain Final State Of ε-NFA Is Final State In NFA

 

Example:-

ε-Closure(q0)-{q0,q1}

ε-Closure(q1)-{q1}

1) Initial State

2) Construction Of δ1

δ1=(q0,0)=ε-Closure(δ(ε-Closure(q0,0)

=ε-Closure(δ({q0,q1},0))

=ε-Closure(q0)

={q0,q1}

 

δ1=(q0,1)=ε-Closure(δ(ε-Closure(q1,1)

=ε-Closure(δ({q0,q1},1))

=ε-Closure(q1)

={q1}

 

δ1=(q1,0)=ε-Closure(δ(ε-Closure(q1,0)

=ε-Closure(δ({q1},0))

=ε-Closure(Φ)

 

δ1=(q1,1)=ε-Closure(δ(ε-Closure(q1,1)

=ε-Closure(δ({q1},1))

=ε-Closure(q1)

={q1}

 

Final State?

q& qBoth Are Final States Because

ε-Closure(q0)={q0,q1}

ε-Closure(q1)={q1}

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *