Nondeterministic finite automaton with ε-moves

In the automata theory, a nondeterministic finite automaton with ε-moves (NFA-ε)(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 provides a convenient way of modeling the systems whose current states are not precisely known. ε-transitions does 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 then 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.

Formal definition

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

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 q1,..., qk such that

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 = a1a2 ... an be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of states, r0,r1, ..., rn, exists in Q with the following conditions:

  1. r0 ∈ E(q0),
  2. ri+1 ∈ E(r') where r' ∈ Δ(ri, ai+1) for each i = 0, ..., n−1, and
  3. rn ∈ F.

In words, the first condition says that the machine starts at the state that is reachable from the start state q0 via ε-transitions. The second condition says that after reading ai, the machine takes a transition of Δ from ri to r', and then takes any number of ε-transitions according to Δ to move from r' to ri+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 = ({s0, s1, s2, s3, s4}, {0, 1}, Δ, s0, {s1, s3}) where the transition relation Δ can be defined by this state transition table:

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 {S1, S2} and the other with states {S3, S4}. 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, Σ,Δ, q0, F) be a NFA-ε. The NFA A' = (Q, Σ, Δ', E(q0), 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.