Nfa With ε-Moves
NFA with ε-moves: In forthcoming constructions it turns out to be useful to extend the notion of NFA by allowing spontaneous transitions. When an NFA executes a spontaneous transition, known as an "-move, it changes its state without reading any input letter. Any number of ε-moves are allowed.
Example: Here's an example of an NFA with ε-moves:
For example, word w = aabbb is accepted as follows: The first a keeps the machine in state 1. Then an ε-move to state 2 is executed, without reading any input. Next, ab is consumed through states 3 and 2, followed by another ε-move to state 4. The last bb keeps the automaton in the accepting state 4.
The automaton of this example accepts any sequence of a's followed by any repetition of ab's followed by any number of b's:
Formally, an NFA with ε-moves (or ε-NFA for short) is A = (Q; Σ; δ; q0; F) where Q, Σ, q0 and F are as before, and ± is a function
Q X (Σ∪{ ε}) -> 2Q
that specifies for each state q the transitions with all input letters a and the empty word ε.
- δ(q; a) is the set of all states p such that there is a move from q to p with input a, and
- δ(q; ε) is the set of states p such that there is a spontaneous move from q to p.
Example:The transition function δfor the ε-NFA of Example 12 is
As in the previous sections, we extend δinto a function ^ δthat gives possible states for all input words:
^ ε: Q X Σ*-> 2Q;
where ^ δ(q;w) is the set of all possible states after the automaton reads input word w, starting at state q. When processing w any number of ε-moves may be used. Before the recursive definition of ^ δwe need to know all states the machine can enter from q without reading any input letters, i.e. using only ε-moves. Let us call this set the ε-CLOSUREof state q.
Example: In the ε-NFA of Example 12 we have
The ε–CLOSURE (q) can be easily found by analyzing which nodes can be reached from state q using only "-moves. This is a simple reachability condition in the directed graph formed by theε-edges, and can be solved effectively by a standard graph algorithm:
If S is any set of states let us denote by ε-CLOSURE (S) the set of states reachable from any element of S using only "-moves, i.e.
Now we are ready to give a recursive definition of ^ δ(q;w):
1. For every state q
(By definition, the ε-CLOSURE consists of all states reachable without consuming any input letter.)
2. For every state q, word w and letter a
The language accepted by ε-NFA A is
