Automata theory -Conversion of ε nfa to nfa

epsilon Non-deterministic and non deterministic equivalence of languages

1. Given: Conversion Of ε -NFA To NFA Note: No Change In Initial State No Change In The Total No. Of States May Be Change In Final States 4 . Changes in Transitions

2. ε- Closure(q0)={q0,q1} ε- Closure(q1)={q1} Let NFA – ε be M=(Q, Σ,δ, q ,F) NFA be M 1 = (Q 1 , Σ,δ 1 , q 1 ,F 1 ) Initial state of given nfa - ε is {q0} Now, initial state of nfa will be {q0} Now find the transition of q0 on inputs 0,1 δ 1 =( q ,0)= ε- Closure( δ(ε- Closure(q ),0)) = ε- Closure( δ({ q ,q 1 },0)) = ε- Closure(q ) ={q ,q 1 } δ 1 =( q ,1)= ε- Closure( δ(ε- Closure(q 1 ),1)) = ε- Closure( δ({ q ,q 1 },1)) = ε- Closure(q 1 ) ={q 1 } δ 1 =( q 1 ,0)= ε- Closure( δ(ε- Closure(q 1 ),0)) = ε- Closure( δ({ q 1 },0)) = ε- Closure( Φ) =Φ   δ 1 =( q 1 ,1)= ε- Closure( δ(ε- Closure(q 1 )1)) = ε- Closure( δ({ q 1 },1)) = ε- Closure(q 1 ) ={q 1 }

3. Resultant NFA is input State 1 *q0 {q ,q 1 } {q 1 } * q1 Φ {q 1 } Final State? q0 & q1 Both are final states because ε-Closure(q0)={q0, q1 } ε-Closure(q1)={ q1 } NFA - Transition diagram NFA - Transition table

4. Example :2 Find δ=( q,a ) Find δ=( q,b ) Find δ=( q,c )

5. Find δ=( r,a ) Find δ=( r,b ) Find δ=( r,c )

6. Find δ=( s,a ) Find δ=( s,b ) Find δ=( s,c )