Question

state a prove the equivalence of NFA and DFA​

Answer 1

Explanation:

We are going to prove that the DFA obtained from NFA by the conversion algorithm accepts the same language as the NFA.

NFA that recognizes a language L is denoted by M1 = < Q1 , , q1,0 , 1 , A1 > and DFA obtained by the conversion is denoted by M2 = < Q2, , q2,0 , 2 , A2 >

First we are going to prove by induction on strings that 1*( q1,0 , w ) = 2*( q2,0 , w ) for any string w. When it is proven, it obviously implies that NFA M1 and DFA M2 accept the same strings.

Theorem: For any string w, 1*( q1,0 , w ) = 2*( q2,0 , w ) .

Proof: This is going to be proven by induction on w.

Basis Step: For w = ,

2*( q2,0 , ) = q2,0 by the definition of 2* .

= { q1,0 } by the construction of DFA M2 .

= 1*( q1,0 , ) by the definition of 1* .

Inductive Step: Assume that 1*( q1,0 , w ) = 2*( q2,0 , w ) for an arbitrary string w. --- Induction Hypothesis

For the string w and an arbitrry symbol a in ,

1*( q1,0 , wa ) =

= 2( 1*( q1,0 , w ) , a )

= 2( 2*( q2,0 , w ) , a )

= 2*( q2,0 , wa )

Thus for any string w 1*( q1,0 , w ) = 2*( q2,0 , w ) holds.

.