Editing Nondeterministic finite automaton (section)

===Equivalence to NFA===

To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε, so it remains to show for every NFA-ε, there exists an equivalent NFA.

Given an NFA with epsilon moves <math>M = (Q, \Sigma, \delta, q_0, F) ,</math>
define an NFA <math>M' = (Q, \Sigma, \delta', q_0, F') ,</math> where
:<math>F' = \begin{cases} F \cup \{ q_0 \} & \text{ if } E(q_0) \cap F \neq \{\} \\ F & \text{ otherwise } \\ \end{cases} </math>
and
:<math>\delta'(q,a) = \delta^*(q,a) </math> for each state <math>q \in Q</math> and each symbol <math>a \in \Sigma ,</math> using the extended transition function <math>\delta^*</math> defined above.

One has to distinguish the transition functions of <math>M</math> and <math>M' ,</math> viz. <math>\delta</math> and <math>\delta' ,</math> and their extensions to strings, <math>\delta</math> and <math>\delta'^* ,</math> respectively.
By construction, <math>M'</math> has no ε-transitions.

One can prove that <math>\delta'^*(q_0,w) = \delta^*(q_0,w)</math> for each string <math>w \neq \varepsilon</math>, by [[mathematical induction|induction]] on the length of <math>w .</math>

Based on this, one can show that <math>\delta'^*(q_0,w) \cap F' \neq \{\}</math> if, and only if, <math>\delta^*(q_0,w) \cap F \neq \{\},</math> for each string <math>w \in \Sigma^* :</math>
* If <math>w = \varepsilon ,</math> this follows from the definition of <math>F' .</math>
* Otherwise, let <math>w = va</math> with <math>v \in \Sigma^*</math> and <math>a \in \Sigma .</math> 
:From <math>\delta'^*(q_0,w) = \delta^*(q_0,w)</math> and <math>F \subseteq F' ,</math> we have <math display=block>\delta'^*(q_0,w) \cap F' \neq \{\} \;\Leftarrow\; \delta^*(q_0,w) \cap F \neq \{\} ;</math> we still have to show the "<math>\Rightarrow</math>" direction.
:*If <math>\delta'^*(q_0,w)</math> contains a state in <math>F' \setminus \{ q_0 \} ,</math> then <math>\delta^*(q_0,w)</math> contains the same state, which lies in <math>F</math>.
:*If <math>\delta'^*(q_0,w)</math> contains <math>q_0 ,</math> and <math>q_0 \in F ,</math> then  <math>\delta^*(q_0,w)</math> also contains a state in <math>F ,</math> viz. <math>q_0 .</math>
:*If <math>\delta'^*(q_0,w)</math> contains <math>q_0 ,</math> and <math>q_0 \not\in F ,</math> but <math>q_0\in F',</math> then there exists a state in <math>E(q_0)\cap F</math>, and the same state must be in <math display=inline>\delta^*(q_0,w) = \bigcup_{r \in \delta^*(q,v)} E(\delta(r,a)) .</math>{{sfn|Hopcroft|Ullman|1979|pp=26-27}}

Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.