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, (Q, \Sigma, \delta, q_0, F), consisting of • a finite
set of
states Q • a finite set of
input symbols called the
alphabet \Sigma • a transition
function \delta : Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow \mathcal{P}(Q) • an
initial (or
start) state q_0 \in Q • a set of states F distinguished as
accepting (or final) states F \subseteq Q. Here, \mathcal{P}(Q) denotes the
power set of Q and \varepsilon denotes empty string.
ε-closure of a state or set of states For a state q \in Q, let E(q) denote the set of states that are reachable from q by following ε-transitions in the transition function \delta, i.e., p \in E(q) if there is a sequence of states q_1,..., q_k such that • q_1 = q, • q_{i+1} \in \delta(q_i, \varepsilon) for each 1 \le i , and • q_k = p. E(q) is known as the
epsilon closure, (also
ε-closure) of q. The ε-closure of a set P of states of an NFA is defined as the set of states reachable from any state in P following ε-transitions. Formally, for P \subseteq Q, define E(P) = \bigcup\limits_{q\in P} E(q).
Extended transition function Similar to NFA without ε-moves, the transition function \delta of an NFA-ε can be extended to strings. Informally, \delta^*(q,w) denotes the set of all states the automaton may have reached when starting in state q \in Q and reading the string w \in \Sigma^* . The function \delta^*: Q \times \Sigma^* \rightarrow \mathcal{P}(Q) can be defined recursively as follows. • \delta^*(q,\varepsilon) = E(q), for each state q \in Q , and where E denotes the epsilon closure; :
Informally: Reading the empty string may drive the automaton from state q to any state of the epsilon closure of q . • \delta^*(q,wa) = \bigcup_{r \in \delta^*(q,w)} E(\delta(r,a)) , for each state q \in Q , each string w \in \Sigma^* and each symbol a \in \Sigma . :
Informally: Reading the string w may drive the automaton from state q to any state r in the recursively computed set \delta^*(q,w); after that, reading the symbol a may drive it from r to any state in the epsilon closure of \delta(r,a) . The automaton is said to accept a string w if :\delta^*(q_0,w) \cap F \neq \emptyset , that is, if reading w may drive the automaton from its start state q_0 to some accepting state in F .
Example for
M Let M 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 M = (\{S_0, S_1, S_2, S_3, S_4\}, \{0, 1\}, \delta, S_0, \{S_1, S_3\}) where the transition relation \delta can be defined by this
state transition table: M can be viewed as the union of two
DFAs: one with states \{S_1, S_2\} and the other with states \{S_3, S_4\}. The language of M can be described by the
regular language given by this
regular expression (1^{*}01^{*}01^{*})^{*} \cup (0^{*}10^{*}10^{*})^{*}. We define M using ε-moves but M 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 M = (Q, \Sigma, \delta, q_0, F) , define an NFA M' = (Q, \Sigma, \delta', q_0, F') , where :F' = \begin{cases} F \cup \{ q_0 \} & \text{ if } E(q_0) \cap F \neq \{\} \\ F & \text{ otherwise } \\ \end{cases} and :\delta'(q,a) = \delta^*(q,a) for each state q \in Q and each symbol a \in \Sigma , using the extended transition function \delta^* defined above. One has to distinguish the transition functions of M and M' , viz. \delta and \delta' , and their extensions to strings, \delta^* and \delta'^* , respectively. By construction, M' has no ε-transitions. One can prove that \delta'^*(q_0,w) = \delta^*(q_0,w) for each string w \neq \varepsilon, by
induction on the length of w . Based on this, one can show that \delta'^*(q_0,w) \cap F' \neq \{\} if, and only if, \delta^*(q_0,w) \cap F \neq \{\}, for each string w \in \Sigma^* : • If w = \varepsilon , this follows from the definition of F' . • Otherwise, let w = va with v \in \Sigma^* and a \in \Sigma . :From \delta'^*(q_0,w) = \delta^*(q_0,w) and F \subseteq F' , we have \delta'^*(q_0,w) \cap F' \neq \{\} \;\Leftarrow\; \delta^*(q_0,w) \cap F \neq \{\} ; we still have to show the "\Rightarrow" direction. :*If \delta'^*(q_0,w) contains a state in F' \setminus \{ q_0 \} , then \delta^*(q_0,w) contains the same state, which lies in F. :*If \delta'^*(q_0,w) contains q_0 , and q_0 \in F , then \delta^*(q_0,w) also contains a state in F , viz. q_0 . :*If \delta'^*(q_0,w) contains q_0 , and q_0 \not\in F , but q_0\in F', then there exists a state in E(q_0)\cap F, and the same state must be in \delta^*(q_0,w) = \bigcup_{r \in \delta^*(q,v)} E(\delta(r,a)) . Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA. ==Closure properties==