Editing Nondeterministic finite automaton (section)

==NFA with ε-moves==

Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA. In this kind of automaton, the transition function is additionally defined on the [[empty string]] ε. A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled "ε". ε-transitions provide a convenient way of modeling systems whose current states are not precisely known: i.e., if we are modeling a system and it is not clear whether the current state (after processing some input string) should be q or q', then we can add an ε-transition between these two states, thus putting the automaton in both states simultaneously.

===Formal definition===
An ''NFA-ε'' is represented formally by a 5-[[tuple]], <math>(Q, \Sigma, \delta, q_0, F)</math>, consisting of
* a finite [[Set (mathematics)|set]] of [[State (computer science)|states]] <math>Q</math>
* a finite set of [[input symbol]]s called the [[Alphabet (computer science)|alphabet]] <math>\Sigma</math>
* a transition [[Function (mathematics)|function]] <math>\delta : Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q)</math>
* an ''initial'' (or [[Finite-state machine#Start state|''start'']]) state <math>q_0 \in Q</math>
* a set of states <math>F</math> distinguished as [[Finite-state machine#Accept .28or final.29 states|''accepting'' (or ''final'') ''states'']] <math>F \subseteq Q</math>.

Here, <math>\mathcal{P}(Q)</math> denotes the [[power set]] of <math>Q</math> and <math>\epsilon</math> denotes empty string.

===ε-closure of a state or set of states===

For a state <math>q \in Q</math>, let <math>E(q)</math> denote the set of states that are reachable from <math>q</math> by following ε-transitions in the transition function <math>\delta</math>, i.e.,
<math>p \in E(q)</math> if there is a sequence of states <math>q_1,..., q_k</math> such that
* <math>q_1 = q</math>,
* <math>q_{i+1} \in \delta(q_i, \varepsilon)</math> for each <math>1 \le i < k</math>, and
* <math>q_k = p</math>.

<math>E(q)</math> is known as the '''epsilon closure''', (also '''ε-closure''') of <math>q</math>.

The ε-closure of a set <math>P</math> of states of an NFA is defined as the set of states reachable from any state in <math>P</math> following ε-transitions. Formally, for <math>P \subseteq Q</math>, define <math>E(P) = \bigcup\limits_{q\in P} E(q)</math>.

===Extended transition function===
Similar to NFA without ε-moves, the transition function <math>\delta</math> of an NFA-ε can be extended to strings.
Informally, <math>\delta^*(q,w)</math> denotes the set of all states the automaton may have reached when starting in state <math>q \in Q</math> and reading the string <math>w \in \Sigma^* .</math>
The function <math>\delta^*: Q \times \Sigma^* \rightarrow \mathcal{P}(Q)</math> can be defined recursively as follows.
* <math>\delta^*(q,\varepsilon) = E(q)</math>, for each state <math>q \in Q ,</math> and where <math>E</math> denotes the epsilon closure;
:''Informally:'' Reading the empty string may drive the automaton from state <math>q</math> to any state of the epsilon closure of <math>q .</math>
* <math display=inline>\delta^*(q,wa) = \bigcup_{r \in \delta^*(q,w)} E(\delta(r,a)) ,</math> for each state <math>q \in Q ,</math> each string <math>w \in \Sigma^*</math> and each symbol <math>a \in \Sigma .</math>
:''Informally:'' Reading the string <math>w</math> may drive the automaton from state <math>q</math> to any state <math>r</math> in the recursively computed set <math>\delta^*(q,w)</math>; after that, reading the symbol <math>a</math> may drive it from <math>r</math> to any state in the epsilon closure of <math>\delta(r,a) .</math> 

The automaton is said to accept a string <math>w</math> if 
:<math>\delta^*(q_0,w) \cap F \neq \emptyset ,</math> 
that is, if reading <math>w</math> may drive the automaton from its start state <math>q_0</math> to some accepting state in <math>F .</math>{{sfn|Hopcroft|Ullman|1979|p=25}}

===Example===
[[Image:NFAexample.svg|thumb|250px|The [[state diagram]] for ''M'']]
Let <math>M</math> be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s. Note that 0 occurrences is an even number of occurrences as well.

In formal notation, let <math display=block>M = (\{S_0, S_1, S_2, S_3, S_4\}, \{0, 1\}, \delta, S_0, \{S_1, S_3\})</math> where
the transition relation <math>\delta</math> can be defined by this [[state transition table]]:
{| class="wikitable" style="margin-left:auto;margin-right:auto; text-align:center;"
! {{diagonal split header|State|Input}}
! 0
! 1
! ε
|-
! ''S''<sub>0</sub>
| {}
| {}
| {''S''<sub>1</sub>, ''S''<sub>3</sub>}
|-
! ''S''<sub>1</sub>
| {''S''<sub>2</sub>}
| {''S''<sub>1</sub>}
| {}
|-
! ''S''<sub>2</sub>
| {''S''<sub>1</sub>}
| {''S''<sub>2</sub>}
| {}
|-
! ''S''<sub>3</sub>
| {''S''<sub>3</sub>}
| {''S''<sub>4</sub>}
| {}
|-
! ''S''<sub>4</sub>
| {''S''<sub>4</sub>}
| {''S''<sub>3</sub>}
| {}
|}
<math>M</math> can be viewed as the union of two [[deterministic finite automaton|DFA]]s: one with states <math>\{S_1, S_2\}</math> and the other with states <math>\{S_3, S_4\}</math>. 
The language of <math>M</math> can be described by the [[regular language]] given by this [[regular expression]] <math>(1^{*}01^{*}01^{*})^{*} \cup (0^{*}10^{*}10^{*})^{*}</math>.
We define <math>M</math> using ε-moves but <math>M</math> can be defined without using ε-moves.

===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.