Theory Of Computation

 Section A

Finite Automata with Null Moves(NFA-ε)R

A Finite Automaton with null moves (FA-ε) does transit not only after giving input from

the alphabet set but also without any input symbol. This transition without input is called

a null move.

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

Q : a finite set of states

Σ : a finite set of input symbols

δ : a transition function δ : Q × (Σ ∪ {ε}) → 2Q

q0 : an initial state q0 ∈ Q

F: a set of final state/states of Q (F⊆Q).

The above (FA-ε) accepts a string set: {0, 1, 01}

Removal of Null Moves from Finite Automata

If in an NDFA, there is ε-move between vertex X to vertex Y, we can remove it using the

following steps:

1. Find all the outgoing edges from Y.

2. Copy all these edges starting from X without changing the edge labels.

3. If X is an initial state, make Y also an initial state.

4. If Y is a final state, make X also a final state.

Problem

Convert the following NFA-ε to NFA without Null move.

Solution

Step 1:

Here the ε transition is between q1 and q2, so let q1 is X and qf is Y.

Here the outgoing edges from qf is to qf for inputs 0 and 1.

Step 2:

Now we will Copy all these edges from q1 without changing the edges from qf and

get the following FA:

Step 3:

Here q1 is an initial state, so we make qf also an initial state.

So the FA becomes -

Step 4:

Here qf is a final state, so we make q1 also a final state.

So the FA becomes -