Proof that NFAs w/epsilon equivalent to NFAs w/o epsilon

We have a NFA w/epsilon, M = (Q,å ,d ,q₀,F). We build a NFA w/o epsilon, M' = (Q,å ,d ',q₀,F') where

• We make the initial state final if in M we can get to a final state from the initial state using only epsilon transitions, i.e.,
• F' = F union {q₀}, if epsilon-closure(q₀) intersect F is nonempty F' = F, otherwise
• d'(q,a) = d^(q,a)

We need to prove that the two machines accept the same input strings, or equivalently, that a given string x is accepted by M' exactly whenever it is accepted by M. By the definitions of acceptance, we want to prove

d'(q₀,x) intersect F' nonempty if d^(q₀,x) intersect F nonempty.

• If x=e, this holds by definition of F'.
• If x=wa,
1. First we prove that d'(q₀,x) = d^(q₀,x) for |x| > 0, by induction on |x|:
• If |x|=1, the equality holds by definition of d'.
• If |x|>1, let x=wa.
1. By definition of d' and by induction,

d'(q₀,wa) = d'(d'(q₀,w),a) = d'(d^ (q₀,w),a)

2. By definition of d' (both the generalized version on sets of states and the normal version),

d'(d^ (q₀,w),a) =
U_{q in d ^(q0 w)} d'(q,a) =
U_{q in d ^(q0 w)} d^(q,a).

3. By the definition of d^,

U_{q in d ^(q0 w)} d^(q,a) = d^(q₀,wa).

• And the conclusion holds by transitivity of equality.
1. Now we prove the two parts of the double implication separately.
• RHS implies LHS: The conclusion holds from the above equality and since F`contains at least the final states in F.
• LHS implies RHS: Exactly one of the following holds.

1. If (d'(q₀,x) intersect F') - {q₀} is nonempty, then d ^(q₀,x) intersect F contains the same non-q₀ states.
2. If d '(q₀,x) intersect F' = {q₀} and q₀ in F, then d^(q₀,x) intersect F = {q₀}.
3. If d '(q₀,x) intersect F' = {q₀} and q₀ not in F, then...
1. By the definition of F', for F and F' to be different, we must have both of the following.

F' = F U{q₀}
e *(q₀) intersect F is nonempty.

2. Since d^(q₀,x) = d'(q₀,x), and by the assumption of this case contains q0,then

q₀  Î d^ (q₀,x).

3. By the definition of d^, d ^ (q₀,x) is also the epsilon-closure of something, so

d^ (q₀,x) Ée*(q₀).

4. Thus, (d^ (q₀,x) ÇF) É(e* (q₀) ÇF) is nonempty.

Exercises:

Q) Construct a NFA without epsilon moves to accept all strings which consist of any number of 0's

followed by any number of 1's followed by any number of 2's

Q) Construct NFA without epsilon moves for

States	a	b	c	e
-->P	f	Q	R	{Q,R}
Q	P	R	{P,Q}	f
*R	f	f	f	f

Q) For the given transition table, Construct the equivalent NFA without epsilon moves

States	a	b	c	e
-->P	P	Q	R	f
Q	Q	R	f	P
*R	R	f	P	Q

Solutions:

Previous Section HOME Next Section