Nondeterministic finite automaton with ε-moves

In the automata theory, a nondeterministic finite automaton with ε-moves (NFA-ε) or e-transition (also known as NFA-λ) is an extension of nondeterministic finite automaton(NFA), which allows a transformation to a new state without consuming any input symbols. The transitions without consuming an input symbol are called ε-transitions or λ-transitions. In the state diagrams, they are usually labeled with the Greek letter ε or λ.

ε-transitions provide a convenient way of modeling the systems whose current states are not precisely known. ε-transitions do not add any extra capacity of recognizing formal languages. NFA-ε's and NFAs recognize same class of formal languages, namely regular languages. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA. Since a NFA-ε can always be transformed into a NFA, the properties are also true for NFAs.

Informal introduction

For example, let's suppose an NFA-ε contains two states, 1 and 2, and it can move to state 2 without consuming any input symbols. If it is in state 1, with the next input symbol, an a, there is an ambiguity: Is the system in state 1 or state 2 before consuming the letter a? Because of this ambiguity, it is more convenient to talk of the set of possible states that the system may be in. Thus, before consuming letter a, the NFA-ε may be in any one of the states of the set {1,2}. Equivalently, one may imagine that the NFA is in state 1 and 2 'at the same time' and this gives an informal hint of the powerset construction that translates an NFA to an equivalent DFA.

In layman's terms

An ε-move is a transition from one state to another that doesn't require any specific condition to be met. For example, a scanner/tokenizer, performing lexical analysis would generally require consuming a character to transition between two states. In the context of NFAs we can create transitions where we don't require any input (unconditional). These are called ε-moves. It's also possible to go from one state to another through more than one ε-move at a time and that this would still be considered a single ε-move. This is important to consider when we want to compute the ε-closure which is just the set of states that are all reachable through any number of ε-moves.

Formal definition

A NFA-ε is represented formally by a 5-tuple, (Q, Σ, Δ, q₀, F), consisting of

• a finite set of states Q
• a finite set of input symbols called the alphabet Σ
• a transition function Δ : Q × (Σ ∪ {ε}) → P(Q)
• an initial (or start) state q₀ ∈ Q
• a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q and ε denotes empty string.

For a q ∈ Q, let E(q) denote the set of states that are reachable from state q by following ε-transitions in the transition function Δ, i.e., p ∈ E(q) iff there is a sequence of states q₁,..., q_k such that

• q₁ = q,
• q_i+1 ∈ Δ(q_i, ε) for each 1 ≤ i < k, and
• q_k = p.

E(q) is known ε-closure of q.

ε-closure is also defined for a set of states. The ε-closure of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following ε-transitions. Formally, for P ⊆ Q, E(P) = ∪_q∈P E(q).

Let w = a₁a₂ ... a_n be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of states, r₀,r₁, ..., r_n, exists in Q with the following conditions:

1. r₀ ∈ E(q₀),
2. r_i+1 ∈ E(r') where r' ∈ Δ(r_i, a_i+1) for each i = 0, ..., n−1, and
3. r_n ∈ F.

In words, the first condition says that the machine starts at the state that is reachable from the start state q₀ via ε-transitions. The second condition says that after reading a_i, the machine takes a transition of Δ from r_i to r', and then takes any number of ε-transitions according to Δ to move from r' to r_i+1. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

It can be shown that ordinary NFA and NFA-ε are equivalent, in that, given either one, one can construct the other, which recognizes the same language.

For more comprehensive introduction of the formal definition see automata theory.

Example

The state diagram 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₀, s₁, s₂, s₃, s₄}, {0, 1}, Δ, s₀, {s₁, s₃}) where the transition relation Δ can be defined by this state transition table:

Input State	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

M can be viewed as the union of two DFAs: one with states {S₁, S₂} and the other with states {S₃, S₄}. The language of M can be described by the regular language given by this regular expression (1*(01*01*)*) ∪ (0*(10*10*)*). We define M using ε-moves but M can be defined without using ε-moves.

Equivalence to NFA and DFA

Let A = (Q, Σ,Δ, q₀, F) be a NFA-ε. The NFA A' = (Q, Σ, Δ', E(q₀), F) is equivalent to A, where for each a ∈ Σ and q ∈ Q, Δ'(q,a) = E( Δ(q,a) ). Subsequently, the NFA can be translated into DFA using powerset construction.

Closure properties

If NFA-εs recognize the languages that are obtained by applying an operation on the NFA-ε recognizable languages then NFA-εs are said to be closed under the operation. The NFA-εs are closed under the following operations.

• Union
• Intersection
• Concatenation
• Negation
• Star
• Kleene closure