NFA with epsilon transition

We extend the class of NFAs by allowing instantaneous ε transitions −

The automaton may be allowed to change its state without reading the input symbol 2.
In diagrams, such transitions are depicted by labeling the appropriate arcs with ε.
Note that this does not mean that E has become an input symbol. On the contrary, we assume that
the symbol E does not belong to any alphabet.

 ε -NFAs add a convenient feature but (in a sense) they bring us nothing new. They do not extend the
class of languages that can be represented.
 Both NFAs and E-NFAs recognize exactly the same languages.

Epsilon (ε) - closure

Epsilon closure for a given state X is a set of states which can be reached from the states X with only
(null) or E moves including the state X itself.
In other words, £-closure for a state can be obtained by union operation of the £-closure of the states
which can be reached from X with a single E move in a recursive manner.

Example
Consider the following figure of NFA with ε move −

The transition state table for the above NFA is as follows −

State 0 1 epsilon

A B,C A B
 State 0 1 epsilon

B - B C

C C C -

For the above example, ε closure are as follows −

 E closure( A) : {A, B,C}

 E closure( B) :{B,C}
 E closure( C) : {C}

How to convert NFA with epsilon to without

epsilon?
In this method, we try to remove all the ε-transitions from the given Non-deterministic finite automata
(NFA) −
The method is mentioned below stepwise −

 Step 1 − Find out all the ε-transitions from each state from Q. That will be called as ε-closure(qi) where,
qi ∈Q.
 Step 2 − Then, 𝛿1 transitions can be obtained. The 𝛿1 transitions means an ε-closure on 𝛿 moves.
 Step 3 − Step 2 is repeated for each input symbol and for each state of given NFA.
 Step 4 − By using the resultant status, the transition table for equivalent NFA without ε can be built.
NFA with ε to without ε is as follows −
δ1(q,a) = ∈ - closure (δ (δ∈^(q,∈𝛜),a)) where, δ^(q,∈𝛜) = ∈ - closure(q)

Example
Convert the given NFA with epsilon to NFA without epsilon.
Solution
We will first obtain ε-closure of each state i.e., we will find ε-reachable states from the current state.
Hence,

 ε-closure(q0) = {q0,q1,q2}
 ε-closure(q1) = {q1,q2}
 ε-closure(q2) = {q2}
ε-closure(q0) means with null input (no input symbol) we can reach q0, q1, q2.
In a similar manner for q1 and q2 ε-closure are obtained.
Now we will obtain 𝛿1 transitions for each state on each input symbol as shown below −
δ'(q0, 0) = ε-closure(δ(δ^(q0, ε),0))
= ε-closure(δ(ε-closure(q0),0))
= ε-closure(δ(q0,q1,q2), 0))
= ε-closure(δ(q0, 0) ∪ δ(q1, 0) U δ(q2, 0) )
= ε-closure(q0 U Φ ∪ Φ)
= ε-closure(q0)
= {q0,q1, q2}

δ'(q0, 1) = ε-closure(δ(δ^(q0, ε),1))

= ε-closure(δ(q0,q1,q2), 1))
= ε-closure(δ(q0, 1) ∪ δ(q1, 1) U δ(q2, 1) )
= ε-closure(Φ ∪q1 U Φ)
= ε-closure(q1)
= {q1, q2}

δ'(q0, 2) = ε-closure(δ(δ^(q0, ε),2))

= ε-closure(δ(q0,q1,q2), 2))
= ε-closure(δ(q0, 2) ∪ δ(q1, 2) U δ(q2, 2) )
= ε-closure(Φ U ΦU q2)
= ε-closure(q2)
= {q2}

δ'(q1, 0) = ε-closure(δ(δ^(q1, ε),0))

= ε-closure(δ(q1,q2), 0))
= ε-closure(δ(q1, 0) U δ(q2, 0) )
= ε-closure(Φ ∪ Φ)
= ε-closure(Φ)
=Φ

δ'(q1,1) = ε-closure(δ(δ^(q1, ε),1))

= ε-closure(δ(q1,q2), 1))
= ε-closure(δ(q1, 1) U δ(q2, 1) )
= ε-closure(q1 ∪ Φ)
= ε-closure(q1)
= {q1,q2}

δ'(q1, 2) = ε-closure(δ(δ^(q1, ε),2))

= ε-closure(δ(q1,q2), 2))
= ε-closure(δ(q1, 2) U δ(q2, 2) )
= ε-closure(Φ ∪ q2)
= ε-closure(q2)
= {q2}

δ'(q2, 0) = ε-closure(δ(δ^(q2, ε),0))

= ε-closure(δ(q2), 0))
= ε-closure(δ(q2, 0))
= ε-closure(Φ)
=Φ
δ'(q2, 1) = ε-closure(δ(δ^(q2, ε),1))
= ε-closure(δ(q2), 1)
= ε-closure(δ(q2, 1))
= ε-closure(Φ)
=Φ

δ'(q2, 2) = ε-closure(δ(δ^(q2, ε),))

= ε-closure(δ(q2), 2))
= ε-closure(δ(q2, 2))
= ε-closure(q2)
= {q2}
Now, we will summarize all the computed δ' transitions as given below −
δ'(q0,0)={q0,q1,q2}
δ'(q0,1)={q1,q2}
δ'(q0,2)={q2}

δ'(q1,0)= { Φ }
δ'(q1,1)={q1,q2}
δ'(q1,2)={q2}

δ'(q2,0)={ Φ }
δ'(q2,1)={ Φ }
δ'(q2,2)={q2}
The transition table is given below −

States\inputs 0 1 2

q0 {q0,q1,q2} {q1,q2} {q2}

q1 Φ {q1,q2} {q2}

q2 Φ Φ {q2}
NFA without epsilon
The NFA without epsilon is given below −

Here, q0, q1, q2 are final states because ε-closure(q0), ε-closure(q1) and ε-closure(q2) contain a
final state q2.

Finite Automata with Output

Mealy machine And Moore machine

Moore machine
Moore Machines are finite state machines with output value and its output depends only on
the present state. It can be defined as (Q, q0, ∑, O, δ, λ) where:
 Q is a finite set of states.
 q0 is the initial state.
 ∑ is the input alphabet.
 O is the output alphabet.
 δ is transition function which maps Q×∑ → Q.
  λ is the output function which maps Q → O.

In the Moore machine shown inabove Figure, the output is represented with each input state sep
arated by /. The lengthof output for a Moore machine is greater than input by 1.

 Input: 11
 Transition: δ (q0,11)=> δ(q2,1)=>q2
 Output: 000 (0 for q0, 0 for q2 and again 0 for q2)

Example 1:
The state diagram for Moore Machine is

Transition table for Moore Machine is:

In the above Moore machine, the output is represented with each input state separated by /. The
output length for a Moore machine is greater than input by 1.

Input: 010

Transition: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2

Output: 1110(1 for q0, 1 for q1, again 1 for q1, 0 for q2)

Example 2:
Design a Moore machine to generate 1's complement of a given binary number.

Solution: To generate 1's complement of a given binary number the simple logic is that if the input is
0 then the output will be 1 and if the input is 1 then the output will be 0. That means there are three
states. One state is start state. The second state is for taking 0's as input and produces output as 1.
The third state is for taking 1's as input and producing output as 0.

Hence the Moore machine will be,

For instance, take one binary number 1011 then

Input 1 0 1 1

State q0 q2 q1 q2 q2

Output 0 0 1 0 0

Thus we get 00100 as 1's complement of 1011, we can neglect the initial 0 and the output which we
get is 0100 which is 1's complement of 1011. The transaction table is as follows:
Thus Moore machine M = (Q, q0, ∑, O, δ, λ); where Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. the
transition table shows the δ and λ functions.

Example 3:
Design a Moore machine for a binary input sequence such that if it has a substring 101, the machine
output A, if the input has substring 110, it outputs B otherwise it outputs C.

Solution: For designing such a machine, we will check two conditions, and those are 101 and 110. If
we get 101, the output will be A, and if we recognize 110, the output will be B. For other strings, the
output will be C.

The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Moore machine becomes:
Example 4:
Construct a Moore machine that determines whether an input string contains an even or odd number
of 1's. The machine should give 1 as output if an even number of 1's are in the string and 0 otherwise.

Solution:

The Moore machine will be:

This is the required Moore machine. In this machine, state q1 accepts an odd number of 1's and state
q0 accepts even number of 1's. There is no restriction on a number of zeros. Hence for 0 input, self-
loop can be applied on both the states.

Example 5:
Design a Moore machine with the input alphabet {0, 1} and output alphabet {Y, N} which produces Y
as output if input sequence contains 1010 as a substring otherwise, it produces N as output.
Solution:

The Moore machine will be:

Mealy Machine
Mealy Machines: Mealy machines are also finite state machines with output value and its o
utput depends on the
present state and current input symbol. It can be defined as (Q, q0, ∑, O, δ, λ’) where:
 Q is a finite set of states.
 q0 is the initial state.
 ∑ is the input alphabet.
 O is the output alphabet.
 δ is the transition function which maps Q×∑ → Q.
 ‘λ’ is the output function that maps Q×∑→ O.
In the mealy machine shown in above
Figure, the output is represented with each input symbol
for eachstate separatedby /. The length of output for a mealy machine is equal to the length
of input.
 Input:11
 Transition: δ (q0,11)=> δ(q2,1)=>q2
 Output: 00 (q0 to q2 transition has Output 0 and q2 to q2 transition also has Output 0)
NOTE: If there are n inputs in the Mealy machine then it generates n outputs while if there
are n inputs in the Moore machine then it generates n + 1 outputs.

Example 1:
Design a Mealy machine for a binary input sequence such that if it has a substring 101, the machine
output A, if the input has substring 110, it outputs B otherwise it outputs C.

Solution: For designing such a machine, we will check two conditions, and those are 101 and 110. If
we get 101, the output will be A. If we recognize 110, the output will be B. For other strings the output
will be C.

The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Mealy machine becomes:
Example 2:
Design a mealy machine that scans sequence of input of 0 and 1 and generates output 'A' if the input
string terminates in 00, output 'B' if the string terminates in 11, and output 'C' otherwise.

Solution: The mealy machine will be:

Conversion from Mealy to Moore Machine

Let us take the transition table of the mealy machine shown in Figure 2.
 Input=0 Input=1

Present Stat Next Stat Next Stat

Output Output
e e e

q0 q1 0 q2 0

q1 q1 0 q2 1

q2 q1 1 q2 0

Table 1
Step 1. First find out those states which have more than 1 output associated with them. q1 a
nd q2 are the states which have both output 0 and 1 associated with them.

Step 2. Create two states for these states. For q1, two states will be q10 (state with output 0
) and q11 (state with output 1). Similarly, for q2, two states will be q20 and q21.
Step 3. Create an empty moore machine with newly generated state. For more machines, O
utput will be associated to each state irrespective of inputs.
Input=0 Input=1

Present State Next State Next State Output

q0

q10

q11

q20

q21

Table 2
Step 4. Fill the entries of next state using mealy machine transition table shown in Table 1.
For q0 on input 0, next
state is q10 (q1 with output 0). Similarly, for q0 on input 1, next state is q20 (q2 with output 0
). For q1 (both q10 and q11) on input 0, next state is q10. Similarly, for q1(both q10 and q11
), next state is q21. For q10, output will be 0 and for q11, output will be 1. Similarly, other e
ntries can be filled.
Input=0 Input=1

Present State Next State Next State Output

q0 q10 q20 0

q10 q10 q21 0

q11 q10 q21 1

q20 q11 q20 0

q21 q11 q20 1

Table 3
This is the transition table of moore machine shown in Figure 1.

Conversion from Moore machine to mealy machine

Let us take the moore machine of Figure 1 and its transition table is shown in Table 3.
Step 1. Construct an empty mealy machine using all states of moore machine as shown in

Table 4.
Input=0 Input=1

Present Stat Next Stat Next Stat

Output Output
e e e

q0

q10

q11
 q20

q21

Table 4
Step 2: Next state for each state can also be directly found from Moore machine transition T
able as:
Input=0 Input=1

Present Stat Next Stat Next Stat

Output Output
e e e

q0 q10 q20

q10 q10 q21

q11 q10 q21

q20 q11 q20

q21 q11 q20

Table 5
Step 3: As we can see output corresponds to each
input in Moore machine transition table. Use this to fill the Output
entries. e.g.; Output corresponding to q10, q11, q20 and q21 are 0, 1, 0 and 1 respectively.
Input=0 Input=1

Present Stat Next Stat Next Stat

Output Output
e e e

q0 q10 0 q20 0

q10 q10 0 q21 1

q11 q10 0 q21 1

 q20 q11 1 q20 0

q21 q11 1 q20 0

Table 6
Step 4: As we can see from table 6, q10 and q11 are similar to each other (same value of n
ext state and Output for
different Inputs). Similarly, q20 and q21 are also similar. So, q11 and q21 can be eliminated.
Input=0 Input=1

Present Stat Next Stat Next Stat

Output Output
e e e

q0 q10 0 q20 0

q10 q10 0 q21 1

q20 q11 1 q20 0

Table 7
This is the same mealy machine shown in Table 1. So we have converted mealy to Moore m
achine and converted back moore to mealy.
Note: Number of statAes in the mealy machine can’t be greater than
number of states in moore machine.
Example: The Finite state machine is
described by the following state diagram with A as starting state, where an arc
label is x / y and x stands for 1-bit input and y stands for 2-bit output?
Outputs the sum of the present and the previous bits of the input.
1. Outputs 01 whenever the input sequence contains 11.
2. Outputs 00 whenever the input sequence contains 10.
3. None of these.
Solution: Let us take different inputs and its output and check which option works:
Input: 01
Output: 00 01 (For 0, Output is 00 and state is A. Then, for 1, Output is 01 and state will be
B)
Input: 11
Output: 01 10 (For 1, Output is 01 and state is B. Then, for 1, Output is 10 and state is C)
As we can see, it is giving the binary sum of thepresent and previous bit. For thefirst bit, the
previous bit is taken as 0.

The difference between the Mealy machine & Moore machine is as follows:

Moore Machine Mealy Machine

Output depends on the present state as well as

Output depends only upon the present state.
present input.

Moore machine also places its output on the

Mealy Machine places its output on the transition.
transition.

More states are required. Less number of states are required.

 There is less hardware requirement for circuit There is more hardware requirement for circuit
implementation. implementation.

They react slower to inputs(One clock cycle later). They react faster to inputs.

Synchronous output and state generation. Asynchronous output generation.

Output is placed on states. Output is placed on transitions.

Easy to design. It is difficult to design.

Moore Machine to Mealy Machine

Algorithm 4
Input − Moore Machine
Output − Mealy Machine
Step 1 − Take a blank Mealy Machine transition table format.
Step 2 − Copy all the Moore Machine transition states into this table format.
Step 3 − Check the present states and their corresponding outputs in the Moore Machine state table;
if for a state Qi output is m, copy it into the output columns of the Mealy Machine state table wherever
Qi appears in the next state.
Example
Let us consider the following Moore machine −

Next State
Present State Output
a=0 a=1

→a d b 1

b a d 0
 c c c 0

d b a 1

Now we apply Algorithm 4 to convert it to Mealy Machine.

Step 1 & 2 −

Next State

Present State a=0 a=1

State Output State Output

→a d b

b a d

c c c

d b a

Step 3 −

Next State

Present State a=0 a=1

State Output State Output

=> a d 1 b 0

b a 1 d 1

c c 0 c 0
 d b 0 a 1

Mealy Machine to Moore Machine

Algorithm 5
Input − Mealy Machine
Output − Moore Machine
Step 1 − Calculate the number of different outputs for each state (Q i) that are available in the state
table of the Mealy machine.
Step 2 − If all the outputs of Qi are same, copy state Q i. If it has n distinct outputs, break Q i into n
states as Qin where n = 0, 1, 2.......
Step 3 − If the output of the initial state is 1, insert a new initial state at the beginning which gives 0
output.
Example
Let us consider the following Mealy Machine −

Next State

Present State a=0 a=1

Next State Output Next State Output

→a d 0 b 1

b a 1 d 0

c c 1 c 0

d b 0 a 1

Here, states ‘a’ and ‘d’ give only 1 and 0 outputs respectively, so we retain states ‘a’ and ‘d’. But
states ‘b’ and ‘c’ produce different outputs (1 and 0). So, we divide b into b0, b1 and c into c0, c1.

Present State Next State Output

 a=0 a=1

→a d b1 1

b0 a d 0

b1 a d 1

c0 c1 C0 0

c1 c1 C0 1

d b0 a 0