Theory of computation

FINITE AUTOMATA
Contents: Introduction, Finite automata and its working ,Types of finite automata, DFA,
NFA,NFA to DFA conversion, NFA with ε- Transitions, NFA with ε to DFA conversion, DFA
minimization , Finite automata with output: Moore machine and Mealy machine, Equivalence of
Moore and Mealy machine: Conversion of Moore machine to Mealy machine, Conversion of
Mealy machine to Moore machine, application of FA.

Finite automata:
A finite automaton is considered to be a mathematical model of a machine or a system. The finite
automaton plays the role of a language acceptor. It takes input string and decides whether the
string will be accepted or rejected. It just produces answer “yes” if machine accepts the string
otherwise it produces “no” answer.

Components of Finite automata:

Finite automata consist of
 Finite set of states
 I/P tape
 Read head.

Working of Finite Automata:

The finite automata consist of finite number of states. The input is stored on input tape. It takes
any string as input and processes it from left to right by reading one symbol at a time. As shown
in figure, there is a head which will point to particular input symbol which can move from left to
right. There will be transitions from one state to another state on reading some input.
Input symbol

Input tape a a b b
Read head

Finite State Control

Figure: Working of Finite Automata

There will be transition from state to state for some input symbol. There will be one initial state
to indicate start state and there will be one or more final states. Final states indicate the
acceptance of the input string. After reading entire string if FA resides in final state then the
input string is accepted otherwise it is rejected. The states other than initial and final states are
called as non-final states.

Prepared By: Rohini Patil Page 1

 Theory of computation

Formal definition:
An FA can be expressed mathematically as,
M= (Q, ∑, δ, q0, F)
where ,
Q: finite set of states
∑: finite set of input symbols
δ: state transition function as, Q X ∑Q
q0: an initial state q0 Q
F: finite set of final states
In automata theory the transition function can be described by following two ways
1] Transition diagram or transition graph
2] Transition table
 Transition diagram or transition graph
A diagrammatical representation of an FA is known as transition diagram. In transition diagram,
a state is represented by a circle, and the transition between states is indicated by directed lines
connecting the circles. Different notation used in transition diagram is as follows.
Initial state

Intermediate state

Final state

Example:

 Transition table:
A transition table is a tabular representation of transition function. The row of the table
corresponds to the state, and the column corresponds to the inputs. The entry for the row
corresponding to state q and the column corresponding to input ‘a’ is the state ∂(q,a).
 In transition table initial state is represented by 
 Final state is represented by ‘*’

Example: In this e.g. states are q1, q2 and input are 0&[Link] q1 state 0 transition goes to q2 state.

Prepared By: Rohini Patil Page 2

 Theory of computation

∑
Q 0 1
q1 q2 q1
q2* q2 q1

Variations of Finite Automata:

FA

FA with final state &no o/p FA with o/p & no final state

NFA DFA MOORE m/c MEALY m/c

Types of FA:
There are two types of FA with no output.
1. Deterministic Finite Automata (DFA)
An finite automata is said to be an deterministic if from every vertex of its transition
graph, there is an unique input symbol which takes the vertex state to the required next
state i.e. there has to be an unique transition on input symbol.

0 1 1
q0 q1

01 0
1
q2

Fig: An DFA accepting all the string that ends with ‘0’

2. Non-Deterministic Finite Automata (NFA)

An finite automata is said to be an non deterministic if there are zero, one or more
transition for an input symbol from a state.
0,1

0 1
q0 q1 q2

Fig: An NFA accepting all the string that ends with ‘01’

Prepared By: Rohini Patil Page 3

 Theory of computation

1] Deterministic Finite Automata (DFA) :

DFA consists of finite set of states. There should be exactly one transition for each i/p symbol
from each state. In DFA from each state on each input symbol The DFA can be expressed
mathematically using a 5-tuple as follows:

Formal definition:
M= (Q, ∑, δ, q0, F)
where ,
Q: finite set of states
∑: finite set of input symbols
δ: transition function as, Q X ∑Q
q0: initial state q0 Q
F: finite set of final states

Examples on DFA:
1] Design a DFA for string containing odd number of a’s.
Solution: Let M= (Q, ∑, δ, q0, F)
∑={a}
The language accepted by this DFA over alphabet , ∑ = { a } is,
L = {a, aaa, aaaaa, aaaaaaa,………}
In a string of a’s no of a’s can be even or odd. so it is represented by 2 states.
Q={q0,q1}

Transition Table: ∑ a
Q
Even no of a’s q0 q1
Odd no of a’s q1* q0

Transition Diagram: a
q0 q1
a

Simulation:
Let L=aaa
δ (q0, aaa)
= δ ( q1, aa)
= δ (q0,a)
= q1 (Accept)

Prepared By: Rohini Patil Page 4

 Theory of computation

2] Design a DFA for language of strings with odd number of a’s and any number of b’s
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { a,b }
The language accepted by this DFA over alphabet , ∑ = { a,b } is
L = {a, ab, ba,bab,aaab, abb, , ……….}
In this string there are two cases as follows:
1. Even number of a’s and any number of b’s (q0 state)
2. Odd number of a’s and any number of b’s (q1 state)
Q = {q0, q1}
Transition Table:
∑
b
Q a
Even a’s any b’s q0 q1 q0
Odd a’s any b’s q1* q0 q1

Transition Diagram:

Simulation:
Let L=baaa
δ (q0,baaa)
= δ ( q0, aaa)
= δ (q1,aa)
= δ (q0,a)
= q1 (Accept)

3] Design a DFA for language of string with odd number of 0’s and even number of 1’s.
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = { 0, 1 } is
L = {011 ,01010, 0101011,……………..}
In this string there are four cases as follows:
1. Even number of 0’s and even number of 1’s (q0 state)
2. Even number of 0’s and odd number of 1’s (q1 state)
3. Odd number of 0’s and even number of 1’s (q2 state)
4. Odd number of 0’s and odd number of 1’s (q3 state)
Q = {q0, q1, q2, q3 }

Prepared By: Rohini Patil Page 5

 Theory of computation

Transition diagram:

Transition table
∑
0 1
Q
q0 q2 q1
q1 q3 q0
q2* q0 q3
q3 q1 q2
Simulation:
Let L=01100
δ (q0,01100)
= δ (q2, 1100)
= δ (q0, 100)
= δ (q2,00)
= δ (q0,0)
= q2 (Accept)
4] Design DFA which accepts string with exactly four alphabets.
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { a,b }
The language accepted by this DFA over alphabet, ∑ = { a,b } is
L = {aaab,baba,bbaa,……………}
As string length is four so it requires five states, .here q5 state is dead state which is used for
satisfying the DFA constraints.
Q={q0.q1,q2,q3,q4,q5}
Transition Diagram:

Prepared By: Rohini Patil Page 6

 Theory of computation

Transition Table:
∑
Q a b

q0 q1 q1

q1 q2 q2

q2 q3 q3

q3 q4 q4

q4* q5 q5

q5 q5 q5
Simulation:
Let L=aaab
δ (q0,aaab)
= δ (q1,aab)
= δ (q2, ab)
= δ (q3,b)
= q4 (Accept)
5] Design DFA for language of string if it ends in a double letter over ∑={a,b}
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { a,b }
The language accepted by this DFA over alphabet, ∑ = { a,b } is
L = {aa,bb,abb,baa,bbaa,……………}
As string ends with double letter so there are two final states one is ending with ‘aa’ and other is
ending with ‘bb’.
Q={q0,q1,q2,q3 }
Transition Diagram:

Prepared By: Rohini Patil Page 7

 Theory of computation

Transition Table:
∑
Q a b

a
q0 q2 q1

b q1 q0 q3
aa
q2* q2 q1

bb q3* q0 q3

Simulation:
Let L=aaabb
= δ (q0,aaabb)
= δ (q2,aabb)
= δ (q2, abb)
= δ (q2,bb)
= δ (q1,b)
= q3(Accept)
6] Design DFA for language of string if it contains at least one occurrence of double letter
over ∑={0,1}
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0, 1} is
L = {00,11,0110,1001,…………..}
As string containing at least one occurrence of double letter means anywhere in the string 00 or
11 should be present, so there are two final states one is with 0 occurrence read as ‘00’ and other
with 1 occurrence as ‘11’.
Q={q0,q1,q2,q3 }
Transition Diagram:

Prepared By: Rohini Patil Page 8

 Theory of computation

Transition Table:
∑
Q 0 1

0 q0 q2 q1

q1 q0 q3
1
00 q2* q2 q2
11 q3* q3 q3

Simulation:
Let L=1001
= δ (q0,1001)
= δ (q1,001)
= δ (q0, 01)
= δ (q2,1)
= q2 (Accept)
7]Design FA for a string does not contain any occurrence of three consecutive b’s.
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { a,b }
The language accepted by this DFA over alphabet, ∑ = {a,b} is
L = {b, bb, bba, a, ab, abb, ababa, …….}
Q = {q0, q1, q2, q3 }
Transition Diagram

Transition Table
∑
Q a b

a q0* q0 q1
b q1* q0 q2

bb q2* q0 q3

bbb q3 q3 q3

Prepared By: Rohini Patil Page 9

 Theory of computation

Simulation:
Let L=ababa
= δ (q0,ababa)
= δ (q0,baba)
= δ (q1, aba)
= δ (q0,ba)
= δ (q1,a)
= q0(Accept)

8] Design FA to accept string that contains at least one occurrence of substring ‘bba’.
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { a,b }
The language accepted by this DFA over alphabet, ∑ = { a,b } is
L = {bba, abba, bbaa, bbba, , bbab, abababbaa, …….}
As FA containg atleast one occurrence of substring ‘bba’ so for reading three alphabet it requires
four states.
Q = {q0, q1, q2, q3 }
Transition Diagram :

Transition Table:
∑
Q a b

a q0 q0 q1
b q1 q0 q2

bb q2 q3 q2

bba q3* q3 q3
Simulation:
Let L=bbba
= δ (q0,bbba)
= δ (q1,bba)
= δ (q2, ba)
= δ (q2,a)
= q3 (Accept)

Prepared By: Rohini Patil Page 10

 Theory of computation

9] Design DFA for string having “101” or “110” as a substring.

Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0,1 } is
L = {101, 110, 0101, 1101, 0110, 1110,0011010, 001100, ……….}
As FA having substring ‘101’ or ‘110’so it requires five states.
Q = {q0, q1, q2, q3, q4}
Transition Diagram:

Transition Table:
∑
Q 0 1

0 q0 q0 q1
1 q1 q2 q4

10 q2 q3 q0
101/110 q3* q3 q3

11 q4 q3 q4

Simulation:
Let L=0110
= δ (q0,0110)
= δ (q0,110)
= δ (q1, 10)
= δ (q4,0)
= q3 (Accept)

Prepared By: Rohini Patil Page 11

 Theory of computation

10] Design DFA to check the i/p is valid if it ends with ‘100’over ∑ = {0,1 }
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0,1 } is
L = {100, 0100, 1100, , 10100, 01100, ,…………….}
For traversing the given sequence 100 from initial state q0 it requires four states.
Q = {q0, q1, q2, q3}

Transition Diagram:

Transition table:
∑
Q 0 1

0 q0 q0 q1

1 q1 q2 q1

10 q2 q3 q1
100 q3* q0 q1

Simulation:
Let L=10100
= δ (q0,10100)
= δ (q1,0100)
= δ (q2,100)
= δ (q1, 00)
= δ (q2,0)
= q3 (Accept)

Prepared By: Rohini Patil Page 12

 Theory of computation

11] Design DFA in which the i/p is valid if it ends in either ‘101’or ‘110’over ∑ = {0,1 }
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0,1 } is
L = {101, 110, 0101, 1101, 0110, 1110, 01101, 10110, ……….}
Q = {q0, q1, q2, q3, q4, q5}
Transition Diagram:

Transition Table:
∑
Q 0 1

0 q0 q0 q1
1 q1 q2 q4

10 q2 q0 q3
101 q3* q2 q4

11 q4 q5 q4
110 q5* q0 q3

Simulation:
Let L=1101
= δ (q0,1101)
= δ (q1,101)
= δ (q4, 01)
= δ (q5,1)
= q3 (Accept)

Prepared By: Rohini Patil Page 13

 Theory of computation

12] Design a FA such that if the second last symbol is ‘a’ over ∑={a,b}
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { a,b }
The language accepted by this DFA over alphabet, ∑ = {a,b } is
L = {aa, ab, abab, abaa, , abaaa, ……….}
As there are two final states one is ending with aa and other is ending with ab because we want
second last symbol is ‘a’.
Q = {q0, q1, q2, q3 }
Transition Diagram:

Transition Table:
∑
Q a b

a q0 q2 q3

b q1 q0 q1

aa q2* q2 q3
ab q3* q0 q1

Simulation:
Let L=abaa
= δ (q0,abaa)
= δ (q2,baa)
= δ (q3, aa)
= δ (q0,a)
= q2 (Accept)

Prepared By: Rohini Patil Page 14

 Theory of computation

13] Design DFA with every odd position of w is ‘1’

Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0,1 } is
L = {101, 111, 1010, 10101, 10111, 11101, 101110, ……….}
Q = {q0, q1, q2}

Transition Diagram:

Transition Table:
∑
Q 0 1

Even 1’s q0* q2 q1

Odd 1’s q1* q0 q0

dead q2 q2 q2

Simulation:
Let L=1010
= δ (q0, 1010)
= δ (q1,010)
= δ (q0, 10)
= δ (q1,0)
= q0 (Accept)
14] Design a DFA to accept language of Set of all strings with odd number of 1’s followed
by even number of 0’s
Solution: Let M= (Q, ∑, δ, q0, F)

∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0,1 } is
L = {100,10000, 11100,111110000, ….}

Prepared By: Rohini Patil Page 15

 Theory of computation

Q = {q0, q1, q2,q3 }

Transition Diagram:

Transition table:
∑
Q 0 1

q0 q3 q1
q1* q2 q0
q2 q1 q3
q3 q3 q3

Simulation:
Let L=100
= δ (q0, 100)
= δ (q1,00)
= δ (q2, 0)
= q1 (Accept)
15] Design a DFA that accepts a set of all strings with which begin and ends with different
letters ∑ = { x, y, z }
Solution: : Let M= (Q, ∑, δ, q0, F)
∑ = { x,y,z }
The language accepted by this DFA over alphabet, ∑ = { x, y, z } is
L = ,xy, xz, zy,zx, yz, yx,xxyz, yxxz, ……….}
Q = {q0, q1, q2, q3, q4, q5, q6,q7,q8}

Transition table:

Prepared By: Rohini Patil Page 16

 Theory of computation

∑
Q x y z

xx q0 q0 q1 q2

xy q1* q0 q1 q2
q1
xz q2* q0 q1 q2
yx q3* q3 q4 q5

yy q4 q3 q4 q5 q3

yz q5* q3 q4 q5

zx q6* q6 q7 q8
q6
zy q7* q6 q7 q8

zz q8 q6 q7 q8

∑
Q x y z

q0 q0 q1 q1

q1* q0 q1 q1

q3* q3 q4 q3

q4 q3 q4 q3

q6* q6 q6 q8

q8 q6 q6 q8

Transition diagram:

Prepared By: Rohini Patil Page 17

 Theory of computation

16]Design DFA for the following language over ∑ = { 0, 1}

L= {x|x begins with ‘1’ and when interpreted as binary integer is a multiple of 5}
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0,1 }
The language accepted by this DFA over alphabet, ∑ = {0,1 } is
L = {101,1010,1111, ……….}
Q = {q0, q1, q2, q3, q4 }

Transition diagram:

Transition table:
∑
Q 0 1

q0* qo q1
q1 q2 q3
q2 q4 q0
q3 q1 q2
q4 q3 q4

Simulation:
Let L=101
= δ (q0, 101)
= δ (q1,01)
= δ (q2, 1)
= q0 (Accept)

17] Design DFA to accept the strings over Σ={a,b}that begins with’aa’ but not ends with
‘aa’.
Solution: Let M= (Q, ∑, δ, q0, F)

Prepared By: Rohini Patil Page 18

 Theory of computation

∑ = { a,b }
The language accepted by this DFA over alphabet, ∑ = {a,b } is
L = {aab,aaba,aabb ……….}
Transition diagram:

Transition table:

18] Design finite state machine to add 2 binary numbers of equal length./To implement
binary adder.
Solution:
I={ (0,0)(0,1)(1,0)(1,1) }
O={0,1}
S={q0,q1}
STF is given as,
∑
(0,0) (0,1) (1,0) (1,1)
Q
q0 q0 q0 q0 q1
q1 q0 q1 q1 q1

MAF is given by,

∑
(0,0) (0,1) (1,0) (1,1)
Q
q0 0 1 1 0
q1 1 0 0 1

Prepared By: Rohini Patil Page 19

 Theory of computation

Transition diagram:

19] Give finite automata accepting (a,b)*(baaa)

Solution:

20]Design finite automata for the string starting with ab

Solution:

21]Design finite automata for the string ending with ‘011’

Soluion:

22]Design finite automata for the having exactly one ‘a’.

Solution:

Prepared By: Rohini Patil Page 20

 Theory of computation

Note: For Divisibility Examples

Tm= (m*base +I/P % no.)
Tm= (m*2 +I/P % no.) for Binary
= (m*3+I/P % no.) for Ternary
= (m*10+I/P % no.) for Decimal
Where m-> current state no.
No -> divisibility number
23] Design a DFA to check whether given decimal number is divisible by 3.
Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
The language accepted by this DFA over alphabet, ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}is
L = {0, 3, 6, 9, 12, 15, 45, ……….}
As the number is divided by 3, the remainder becomes either 0 or 1 or 2.
q0 -> Gives Remainder zero for input 0 or 3 or 6 or 9
q1 -> Gives Remainder 1 for input 1 or 4 or 7
q2 -> Gives Remainder 2 for input 2 or 5 or 8
Q = {q0, q1, q2}
Transition Table:
∑
Q {0,3,6,9} {1,4,7} {2,5,8}

q0* q0 q1 q2

q1 q1 q2 q0
q2 q2 q0 q1

Transition Diagram:

Simulation:
Let L=363
= δ (q0, 363)
= δ (q0,63)
= δ (q0, 3)
= q0 (Accept)

Prepared By: Rohini Patil Page 21

 Theory of computation

24] Design divisibility by 4 tester FSM for binary numbers.

Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0, 1}
The language accepted by this DFA over alphabet, ∑ = {0, 1}is
L = {000, 100, 1000, 1110, ……….}
When the number is divided by 4, the remainder is either 0 or 1 or 2 or 3.
For constructing DFA, string may have following four different possibilities:
1. Remainder is 0 (state q0) therefore it is final state.
2. Remainder is 1 (state q1)
3. Remainder is 2 (state q2)
4. Remainder is 3 (state q3)
Q = {q0, q1, q2, q3}
Transition Diagram:

Transition Table:
∑
Q 0 1

q0* q0 q1

q1 q2 q3

q2 q0 q1

q3 q2 q3

Simulation:
Let L=1100
= δ (q0, 1100)
= δ (q1,100)
= δ (q3, 00)
= δ (q2, 0)
= q0 (Accept)

Prepared By: Rohini Patil Page 22

 Theory of computation

25] Design a DFA to check whether given ternary number is divisible by 5.

Solution: Let M= (Q, ∑, δ, q0, F)
∑ = { 0, 1,2}
The language accepted by this DFA over alphabet, ∑ = {0, 1,2}is
L = {0, 101, 221, 2102, ……….}
When the number is divided by 5, the remainder is either 0 or 1 or 2 or 3 or 4.
For constructing DFA, string may have following four different possibilities:
1. Remainder is 0 (state q0) therefore it is final state.
2. Remainder is 1 (state q1)
3. Remainder is 2 (state q2)
4. Remainder is 3 (state q3)
5. Remainder is 4 (state q4)
Q = {q0, q1, q2, q3, q4}

Transition Table:
∑
Q 0 1 2

 q0* q0 q1 q2

q1 q3 q4 q0

q2 q1 q2 q3

q3 q4 q0 q1

q4 q2 q3 q4
Transition Diagram:

Simulation:
Let L=2102
= δ (q0, 2102)
= δ (q2,102)
= δ (q2, 02)
= δ (q1, 2)
= q0 (Accept)

Prepared By: Rohini Patil Page 23

 Theory of computation

26] Design a DFA to check whether given unary number is divisible by 3.

Solution: Unary number has only one alphabet symbol which may be a digit or character.
∑ = {0}
In unary number system representation is like,
10
200
3000
The language accepted by this DFA is
L = {0,00,000, ….}
For constructing DFA, string may have following four different possibilities:
1. Remainder is 0 (state q0) therefore it is final state.
2. Remainder is 1 (state q1)
3. Remainder is 2 (state q2)
Q = {q0, q1, q2}
Similar to above example transitions are added on each state for all input symbols.
Transition Diagram

Transition Table:
∑
Q 0

q0* q1

q1 q2

q2 q0

2] Non deterministic Finite Automata (NFA) :

NFA consists of finite set of states. There should be one start state and one or more final states.
In NFA from each state on each i/p symbol there can be 0,1 or more transition. The NFA can be
expressed mathematically using a 5-tuple as follows:
Formal definition: M= (Q, ∑, δ, q0, F)
where ,
Q: finite set of states
∑: finite set of input symbols
δ: transition function as, Q X ∑2Q
q0: initial state q0 Q
F: finite set of final states

Prepared By: Rohini Patil Page 24

 Theory of computation

Example:
Transition Diagram: Transition table:

∑
0 1
Q

qA qA qB

qB ϕ {qB,qC}

qC* qB qA

In above diagram or from transition table we see that there are from qB to 1 transition goes to
two different states.
Difference between DFA and NFA
DFA NFA
It is deterministic It is non-deterministic
For each state for given input symbol For each state for given input symbol
there is only one transition. there can be 0,1 or more transition.

Transition function is defined as, Transition function is defined as,

δ = Q X ∑Q δ = Q X ∑2Q
No epsilon transition Epsilon transitions are allowed

No multiple moves Multiple moves are allowed

No missing transitions Missing transitions are allowed

Complex to design Simpler to design

Example Example

Equivalence of NFA and DFA :

A DFA can simulate the behavior of NFA by increasing the no. of states. For every NFA there
exists equivalent DFA which accepts the same language. So we can convert the given NFA to its
equivalent DFA.
NFA to DFA conversion Steps:
 Start with initial state of given NFA.
 For each input symbol find the transitions of state l.
 If any new state is encountered then add it to DFA and GOTO step 2.

Prepared By: Rohini Patil Page 25

 Theory of computation

 Repeat this procedure till no new state is encountered.

Example 1: Consider NFA as M=({q0,q1}, {0,1}, δ, q0, {q1})into equivalent DFA, where
δ is given by,

∑
0 1
Q

q0 {q0,q1} {q1}

q1 * ϕ {q0,q1}

Solution:
1. As, δ(q0,0)={q0,q1} -------New state
δ(q0,1)={q1}
2. δ({q0,q1},0)= δ(q0,0) U δ(q1,0)={q0,q1}U ϕ = {q0,q1}
δ({q0,q1},1)= δ(q0,1) U δ(q1,1)={q0,q1}U {q1}= {q0,q1}
δ(q1, 0)= ϕ
δ(q1,1)= {q0,q1}----already exists
3. Here no new state is generated so we will stop here. Here ‘q1’ is final state so every
combination with state’q1’ will become final state. The transition table is shown below.
∑
0 1
Q
q0 {q0,q1} {q1}

q1* ϕ {q0,q1}

{q0,q1}* {q0,q1} {q0,q1}

Example 2: Consider NFA as M=({q0,q1,q2}, {0,1}, δ, q0, {q1})into equivalent DFA, where
δ is given by,

∑
0 1
Q

q0 {q0,q1} {q2}

q1 * {q1} {q1}

q2 ϕ {q1,q2}

Prepared By: Rohini Patil Page 26

 Theory of computation

Solution:
1. As, δ(q0,0)={q0,q1} -------New state
δ(q0,1)={q2}
2. δ({q0,q1},0)= δ(q0,0) U δ(q1,0)={q0,q1}U ϕ = {q0,q1}
δ({q0,q1},1)= δ(q0,1) U δ(q1,1)={q2}U {q1}= {q2,q1}-------New state
3. δ({q2,q1},0)= {q1}
δ({q2,q1},1)={q1,q2}
4. δ(q1, 0)= {q1}
δ(q1,1)= {q1}
δ(q2, 0)= ϕ
δ(q2,1)= {q1,q2}

The transition table is shown below.

∑
0 1
Q
q0 {q0,q1} {q2}

q1* {q1} {q1}

q2 ϕ {q1,q2}

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

{q1,q2}* {q1} {q1,q2}

DFA minimization:
The DFA can be minimized if it consists of equivalent states. If their both transition are
equivalent then that state can be merged. The rules for the minimization are:
1. Initial state cannot be replaced by any other state.
2. Replace one final state by its equivalent final state only.
3. Replace one non-final state by its equivalent non-final state only.
Example : Convert following NFA to equivalent DFA
M=({p,q,r,s}, {0,1}, δ, p, {s}) δ is given in following table
∑
0 1
Q
p {p,q} p
q r r

Prepared By: Rohini Patil Page 27

 Theory of computation

r s ϕ
s* s s
Solution:
1. δ(p,0)={p, q} -----New state
δ(p,1)=p
2. δ({p,q},0) = {p,q,r}-----New state
δ({p,q},1) ={p,r}-----New state
3. δ({p,q,r},0) = {p,q,r,s}-----New state
δ({p,q,r},1) = {p,r}
4. δ({p, r},0) = {p,q,s}-----New state
δ({p, r},1) = {p}
5. δ({p,q,r,s},0) = {p,q,r,s}
δ({p,q,r,s},1) = {p,r,s}-----New state
6. δ({p,q,s},0) = {p,q,r,s}
δ({p,q,s},1) = {p,r,s}
7. δ({p,r,s},0) = {p,q,s}
δ({p,r,s},1) = {p,s}-----New state
8. δ({p, s},0) = {p,q,s}
δ({p, s},1) = {p,s}
The transition table is:
∑
0 1
Q
p {p,q} p
q r r
r s ϕ
s* s s
{p,q} {p,q,r} {p,r}
{p,q,r} {p,q,r,s} {p,r}
{p,r} {p,q,s} p
{p,q,r,s}* {p,q,r,s} {p,r,s}
{p,q,s}* {p,q,r,s} {p,r,s}
{p,r,s}* {p,q,s} {p,s}
{p,s}* {p,q,s} {p,s}

Prepared By: Rohini Patil Page 28

 Theory of computation

In above DFA state {p,r,s} {p,s}

{p,q,r,s} {p,q,s}.
The modified table after replacement is given below.

∑
0 1
Q
p {p,q} p
q r r
r s ϕ
s* s s
{p,q} {p,q,r} {p,r}
{p,q,r} {p,q,s} {p,r}
{p,r} {p,q,s} p
{p,q,s}* {p,q,s} {p,s}
{p,s}* {p,q,s} {p,s}
{p,q,s} {p,s} Resultant table is:
∑
0 1
Q
A p {p,q} p
B q r r
C r s ϕ
D s* s s
E {p,q} {p,q,r} {p,r}
F {p,q,r} {p,s} {p,r}
G {p,r} {p,s} p
H {p,s}* {p,s} {p,s}

Example : Convert the following NFA to DFA DEC-2011

M=({p,q,r,s,t}, {0,1}, δ, p, {s,t}) δ is given in following table

Prepared By: Rohini Patil Page 29

 Theory of computation

∑
0 1
Q
p {p,q} p
q {r, s} t
r {p,r} t
s* ϕ ϕ
t* ϕ ϕ
Solution:
1. δ({p,q},0) = {p,q,r,s}------New state
δ({p,q},1) = {p,t}-----New state
2. δ({r,s},0) = {p,r}-----New state
δ({r,s},1) = {t}-----New state
3. δ({p,q,r,s},0) = {p,q,r,s}
δ({p,q,r,s},1) = {p,t}
4. δ({p, t},0) = {p, q}
δ({p, t},1) = {p}
5. δ({p,r},0) = {p,q,r}----New state
δ({p,r},1) ={p,t}
6. δ({p,q,r},0) = {p,q,r,s}
δ({p,q,r},1) = {p,t}
Transition table for DFA is
∑
0 1
Q
p {p,q} p

q {r, s} t

r {p,r} t

s* ϕ ϕ

t* ϕ ϕ

{p,q} {p,q,r,s} {p,t}

{r,s}* {p,r} t

{p,r}* {p,q,r} {p,t}

Prepared By: Rohini Patil Page 30

 Theory of computation

{p,q,r,s}* {p,q,r,s} {p,t}

{p,t} {p,q} p

{p,q,r}* {p,q,r,s} {p,t}

In above DFA state {p,q,r},{p,q,r,s} {p,q,r,s}

{r,s} {r}.

∑
0 1
Q
 p {p,q} p

q r t

r {p,r} t

s* ϕ ϕ

t* ϕ ϕ

{p,q} {p,q,r,s} {p,t}

{p,r}* {p,q} {p,t}

{p,q,r,s}* {p,q,r,s} {p,t}

{p,t} {p,q} p

Example: Convert the given NFA to equivalent DFA

M=({p,q,r,s}, {0,1}, δ, p, {q,s}) δ is given in following table
∑
0 1
Q

p {q,r} q

q* r {q,r}

r s p

s* ϕ p

Prepared By: Rohini Patil Page 31

 Theory of computation

Solution:
1. δ(p,0)={q, r} -------New state
δ(p,1)=q
2. δ({q,r},0) = {r,s}-------New state
δ({q,r},1) ={p,q,r}-------New state
3. δ(q,0)={r}
δ(q,1)={q, r}
4. δ({r,s},0) = {s}
δ({r,s},1) = {p}
5. δ({p,q,r},0) = {q,r,s}-------New state
δ({p,q,r},1) = {p,q,r}
6. δ(r,0)={s} δ(r,1)={p}
7. δ({q,r,s},0) = {r,s}
δ({q,r,s},1) = {p,q,r}
8. δ(s,0)= ϕ δ(s,1)={p}
The transition table for DFA is given in figure
∑
0 1
Q
p {q,r} q

q* r {q,r}

r s p

s* ϕ p

{q,r}* {r,s} {p,q,r}

{r,s}* s p

{p,q,r}* {q,r,s} {p,q,r}

{q,r,s}* {r,s} {p,q,r}

Hence the minimized DFA is:

Prepared By: Rohini Patil Page 32

 Theory of computation

∑
0 1
Q
p {q,r} q

q* r {q,r}

r s p

s* Φ p

{q,r}* {s} {p,q,r}

{p,q,r}* {q,r} {p,q,r}

NFA with ε- Transitions:
It is an NFA including transitions on the empty input i.e. ε

 In ε-closure of q0 the state q0 itself .

 There is a path with label ‘ε’ from q0 to q1 so {q1} is included.
 There is a path with label ‘ε’ from q1 to q2 i.e. there is ε-path from q0 to q2 indirectly
as q0q1q2.
Therefore ε-closure of q0={q0,q1,q2}
Similarly ε-closure of q1={q1,q2}
ε-closure of q2={q2}
Steps :
1. Find the ε-closure of a state.
2. For each subset in ε-closure find transitions for each input symbol
3. Repeat above two steps till no new state is encountered.

Example 1: Convert the given ε-NFA to equivalent minimized DFA.

∑
ε a b c
Q

p Φ p q r

q p q r Φ

r* q r Φ P

Prepared By: Rohini Patil Page 33

 Theory of computation

Solution:
1. ε-closure of p={p}
ε-closure of q={p, q}
ε-closure of r={p, q, r}
2. δ({p}, a)= ε-closure { δ (ε-closure p),a}={p  p }={p}
δ({p}, b)= ε-closure { δ (ε-closure p),b}={p  q }={p q}
δ({p}, c)= ε-closure { δ (ε-closure p),c}={p  r }={p r}
3. δ({q}, a)= ε-closure { δ (ε-closure q),a}
= ε-closure (δ {p q},a)
={pq}
δ({q}, b)= ε-closure { δ (ε-closure q),b}
= ε-closure (δ {pq},b)
={pqr]
δ({q}, c)= ε-closure { δ (ε-closure q),c}
= ε-closure (δ {pq},c)
={pqr}
4. δ({r}, a)= ε-closure { δ (ε-closure r),a}
= ε-closure (δ {pqr},a)
={p qr}
δ({r}, b)= ε-closure { δ (ε-closure r),b}
= ε-closure (δ {pqr},b)
={pqr}
δ({r}, c)= ε-closure { δ (ε-closure r),c}
= ε-closure (δ {pqr},c)
={pqr}
Following table shows NFA without ε moves.
∑
a b c
Q

p p pq pqr

q pq pqr r

r* pqr pqr pqr

If we have to convert into equivalent DFA then use the NFA to DFA conversion method.

Prepared By: Rohini Patil Page 34

 Theory of computation

Example2: Convert the given ε-NFA to equivalent DFA.

∑
ε a b c
Q
p {q,r} Φ q r

q Φ p r {p,q}

r* Φ Φ Φ Φ

Solution:
1. ε-closure of p={p, q, r}
ε-closure of q={q}
ε-closure of r={r}
2. δ({p}, a)= ε-closure { δ (ε-closure p),a}
= ε-closure (δ {pqr},a)
= ε-closure (Φ  p  Φ)
={pqr}
δ({p}, b)= ε-closure { δ (ε-closure p),b}
= ε-closure (δ {pqr},b)
= ε-closure (q  r  Φ) ={qr}
δ({p}, c)= ε-closure { δ (ε-closure p),c}
= ε-closure (δ {pqr},c)
= ε-closure (r  pq  Φ)
={pqr}
3. δ({q}, a)= ε-closure { δ (ε-closure q),a}
= ε-closure (δ { q},a)
= ε-closure (p)
={pqr}
δ({q}, b)= ε-closure { δ (ε-closure q),b}=
= ε-closure (δ {q},b)
= ε-closure (r)
={r}
δ({q}, c)= ε-closure { δ (ε-closure q),c}
= ε-closure (δ {q},b)
= ε-closure (pq)
={pqr}
4. δ({r}, a)= ε-closure { δ (ε-closure r),a}
= ε-closure (δ {r}a)

Prepared By: Rohini Patil Page 35

 Theory of computation

=Φ
δ({r}, b)= ε-closure { δ (ε-closure r),b}
= ε-closure (δ {r},b)
=Φ
δ({r}, c)= ε-closure { δ (ε-closure r),c}
= ε-closure (δ {r},c)
=Φ
Following table shows NFA without ε moves.
∑
a b c
Q

p pqr qr pqr

q pq r pqr

Φ Φ Φ
r*

Minimization of DFA (Using BOX Method)

We can found the equivalent states from the transition table and can reduce it. The problem with
this method is that sometimes it requires repetitive reductions or more number of [Link]
method minimizes the DFA within one step.
Steps for Minimization method:
 Remove unreachable states, i.e. states which cannot be reached from the start state
 Create a table such that Rows and columns will be identified by the state.
 Put ‘X’ for row and column of final state
 Check for equivalence state .
For pair (p, q) and input ‘a’ and ‘b’
If δ(p, a) =r and δ(q, a) =s
 If r!= s and for(r, s) pair ‘X’ is there then put ‘X’ for (p, q)
 If r!= s and for(r, s) pair ‘X’ is not there then do not put ‘X’ for (p, q)
 If r==s then check for next input and repeat above two steps
If δ(p, a) =δ(q, a) =r
If δ(p, b)= δ(q, b) =s
 Two states (p,q) cannot be equivalent if one is a final state and the other is not.
 Then pair (p, q) is equivalent and do not put ‘√’ for (p, q).
 Repeat the above steps .

Prepared By: Rohini Patil Page 36

 Theory of computation

Example 1: Minimize the DFA represented by transition diagram below.

∑
Q 0 1

A B F
B G C
C* A C
D C G
E H F
F C G
G G E
H G C

 From above table put ‘X’ for row and column of final state

C X X

D X

E X

F X

G X

H X

A B C D E F G

 Now, start with last column with pair (G,H)

δ(G,0) =G δ(G,1)=E
δ(H,0) =G δ(H,1)=C

Prepared By: Rohini Patil Page 37

 Theory of computation

For (E, C) pair, there is already ‘X’ in table so put ‘X’ in (G, H) column.
 Next take the pair (F, H)
δ(F,0) =C
δ(H,0) =G
For (C, G) pair, one is final state and other is non final so put ‘X’ in table
 Next take the pair (F, G)
δ(F,0) =C
δ(G,0) =G
For (C, G) pair, one is final state and other is non final so put ‘X’ in table
The above procedure is repeated for remaining pair.
 For (D, F) pair
δ(D,0) = δ(F,0) =C
δ(D,1)= δ(F,1)=G
As both transitions are equal put ‘√’.
 Similarly ,
δ(B,0) = δ(H,0) =G
δ(B,1)= δ(H,1)=C
As both transitions are equal put ‘√’.
 For (A, E) pair
δ(A,1) = δ(E,1) =F
δ(A,0)=B and δ(E,1)=H
As, for (B, H) pair we have already marked as equivalent pair so put ‘√’ for (A, E) pair.
B X

C X X

D X X X

E √ X X X

F X X X √ X

G X X X X X X

H X √ X X X X X

A B C D E F G
We get following equivalent pairs as (D, F) ,(B, H) and (A, E)
Thus the minimized DFA is :

Prepared By: Rohini Patil Page 38

 Theory of computation

∑
0 1
Q
A B F
B G C
C* A C
F C G
G G A

Example 2: Minimize the following DFA

∑ 0 1
Q

A B C

B D E

C F G

D D E

E F G

F* D E

G F G

Solution:

Prepared By: Rohini Patil Page 39

 Theory of computation

B √

C X X

D √ √ X

E X X √ X

F X X X X X
G X X √ X √ X
A B C D E F
The equivalent pairs we get are (AB),(AD)(BD) (A ,B,D)
(EG),(CG),(CE) (C,E,G)
(A ,B,D) (C,E,G),F
The minimized DFA is,

∑ 0 1
Q

A A C

C F C

F* A C

Example 3: Find a minimum state finite automata equivalent to following automata

∑
a b
Q
q0 q1 q3
q1 q0 q3
q2 q1 q4
q3* q5 q5
q4 q3 q3
q5* q5 q5

Note: if more than one final states are there then do not put ‘X’ for their combination. First
check the transitions and then decide.

Solution: Here two final states i.e.q3,q5 so put ‘X’ for row and column of q3 and q5.

Prepared By: Rohini Patil Page 40

 Theory of computation

While doing this, we will not put ‘X’ for (q3, q5) pair.
Because, δ(q3,a) = δ(q5,a) =q5
δ(q3,b)= δ(q5,b)=q5
Both transitions are equal.
q1 X

q2 X X

q3 X X X

q4 X X X X

q5 X X X √ X

q0 q1 q2 q3 q4
The minimized DFA is:
∑ a b
Q

q0 q1 q3

q1 q0 q3

q2 q1 q4

q3* q3 q3

q4 q3 q3

Example 4: Find a minimum state finite automata equivalent to following automata.

∑
0 1
Q
a b a
b a c
c d b
d* d a
e d f
f g e
g f g
h h d

Solution: The table for above DFA shown below.

Prepared By: Rohini Patil Page 41

 Theory of computation

b X

c X X

d X X X

e X X X X

f X X X X X

g X X X X X X
h X X X X X X X
a b c d e f g
As equivalent states are not present in above DFA, so it cannot be minimized any more. Hence
given DFA is minimized DFA

Example 5: Find a minimum state finite automata equivalent to following automata.

Solution: As we see F is not reachable from ‘A’ so we eliminate F

Transition table:
∑ 0 1
B X
Q
C X X
A B C
D √ X X
B B D
E X X √ X
C* B C
A B C D
D B E

E* B C

After constructing table we get two pair that are equivalent i.e.(A,D) and (C,E)therefore there are
three states (A,D) (C,E),B

Prepared By: Rohini Patil Page 42

 Theory of computation

The minimized DFA is ,

∑ 0 1
Q

A B C

B B A

C* B C

Here state A and C cannot be merged because one is final and other is non final.

Finite Automata with Output:

As we see Finite automata doesn’t include information about output. If FA resides in final state
then the string is accepted otherwise it is rejected. There are two different types of machines
which can be formulated as Finite Automata with Output, Such machines do not have final
states. Both machine generates output for every input and can be categorized as,
1. Moore machine
2. Mealy machine.

 Moore Machine:
It is a machine with finite no of states and for which output symbol at a given time depends on
present state of machine. In Moore machine the output symbol is associated with each state.
Formal definition: A Moore machine can be expressed as,
M=(Q,∑,∆,δ,λ ,q0)
Q : Finite set of states
∑: Input alphabet
∆:Output alphabet
δ: State transition function Q X ∑ Q
λ: Machine function/Output Function Q ∆
q0: initial state
Example:
State transition Diagram: Transition Table:
∑
0 1 o/p
Q
qA qA qB a

qB qC qB b

qC qB qA a

Prepared By: Rohini Patil Page 43

 Theory of computation

 Mealy Machine:
It is a machine with finite no of states and for which output symbol at a given time depends on
present input symbol and present state of machine. In Mealy machine the output symbol is
associated with each transition.
Formal definition: A Mealy machine can be expressed as,
M=(Q,∑,∆,δ,λ ,q0)
Q : Finite set of states
∑: Input alphabet
∆:Output alphabet
δ: State transition function Q X ∑ Q
λ: Machine function/Output Function Q X ∑  ∆
q0: initial state
Example:

State transition Table δ= Output table λ=

∑ ∑
0 1 0 1
Q Q
qA qA qB qA a c

qC qB b a
qB qB
qC qA qB qC c b

1] Design Moore and Mealy machine to find 1’s complement of a binary number .
Solution:
Moore Machine: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={0,1}
As we have two output symbols so require two states to represent them.
Hence Q={q0,q1}

Prepared By: Rohini Patil Page 44

 Theory of computation

q0 which gives output “0” .

q1 which gives output “1” .
Transition Table:
∑
0 1 o/p
Q
q0 q1 q0 0

q1 q1 q0 1

Transition Diagram:

Mealy Machine:
For mealy machine we require just two transitions. One is to convert 0 to 1 and other to convert 1
to 0.
State transition table δ= Output table λ=
∑ ∑
0 1 0 1
Q Q
q0 q0 0
q0 q1 1
q0 q1 1 0
q1 q1

Transition Diagram:

2] Design Moore and Mealy machine consisting of strings from from ∑ * , where ∑ ={0,1} ,
and ending with “00” or “11” OR (0+1)*(00+11)
Solution: Let ∑ ={0,1}
Let us assume ,∆={Y,N}
If string is accepted it gives “Y” output otherwise it gives “N” output.

Prepared By: Rohini Patil Page 45

 Theory of computation

Moore Machine: We have to check whether the string is ending with “00” or “11”.

Transition table:
∑
0 1 o/p
Q
q0 q1 q3 n

q1 q2 q3 n

q2 q2 q3 y

q3 q1 q4 n

q4 q1 q4 y

Mealy Machine:
State transition table δ= Output table λ=
∑ ∑
0 1 0 1
Q Q
q0 q1 q2 q0 n n

q2 q1 y n
q1 q1
q2 q2 n y
q2 q1

Transition Diagram:

Prepared By: Rohini Patil Page 46

 Theory of computation

3] Design Moore and Mealy machine for the following:

For input from ∑ * , where ∑ ={0,1} , If input ends with 101,output should be A , If input
ends with 110 then output is B Otherwise output should be C.
Solution:
Moore Machine:Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={A,B,C}
Transition Table
∑ o/p
0 1
Q
0 C
q0 q0 q1

1 C
q1 q2 q4

10 C
q2 q0 q3

101 A
q3 q2 q4

11 C
q4 q5 q4

110 B
q5 q0 q3

Transition diagram:

Prepared By: Rohini Patil Page 47

 Theory of computation

Mealy Machine:
State transition table δ= Output table λ=

∑ ∑
0 1 0 1
Q Q
q0 q0 q1 q0 C C
q1 q2 q4 q1 C C
q2 q0 q3 q2 C A
q3 q2 q4 q3 C C
q4 q5 q4 q4 B C
q5 q0 q3 q5 C A

Transition diagram:

Prepared By: Rohini Patil Page 48

 Theory of computation

4] Design Moore and Mealy machine for finding Residue mod 3 for binary numbers.
Solution:
May-14(CBGS)
Moore Machine: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={0,1,2}
When the number is divided by 3, the remainder is either 0 or 1 or 2.
For constructing DFA, string may have following four different possibilities:
1. Remainder is 0 (state q0)
2. Remainder is 1 (state q1)
3. Remainder is 2 (state q2)

Transition Diagram: Transition Table:

∑ o/p
Q 0 1

q0 q0 q1 0

q1 q2 q0 1

q2 q1 q2 2

Mealy Machine:
State transition table δ= Output table λ=
∑ ∑
0 1 0 1
Q Q
q0 q0 q1 q0 0 1
q1 q2 q0 q1 2 0
q2 q1 q2 q2 1 2
Transition Diagram:

Prepared By: Rohini Patil Page 49

Dec-14(CBGS)
 Theory of computation

5]Design Moore and Mealy machine to Decrement a binary number.

Solution:
Mealy Machine: Let M=(Q,∑,∆,δ, λ ,q0) be the required machine.
∑={0,1}
∆={0,1}
Q={q0,q1 }
When binary number is decremented then trailing 1’s become 0 and 0 become 1and after
trailing 1’s remaining bits are same.[start from MSB bit]
Example: if input 1011 then output becomes 1010
if input 111 then output becomes 110

State transition table δ= Output table λ=

∑ ∑
0 1 0 1
Q Q
q0 q0 q1 q0 1 0
q1 q1 q1 q1 0 1
Transition Diagram:

Moore machine: As output to state q1 are different therefore this state is splitted as [q10] and
[q11]
Transition diagram: Transition Table:

∑ o/p
Q 0 1

q0 q0 q10 0

q10 q10 q11 0

q11 q10 q11 1

Prepared By: Rohini Patil Page 50

 Theory of computation

6] Design Mealy machine to Increment a binary number.

Solution:
Mealy Machine: Let M=(Q,∑,∆,δ, λ ,q0) be the required machine.
∑={0,1}
∆={0,1}
Q={q0,q1}
When binary number is incremented then trailing 1’s become 0 and the first 0 immediately
before trailing 1’s become1.
Example: if input 1011 then output becomes 1100
State transition table δ= Output table λ=
∑ ∑
0 1 0 1
Q Q
q0 q1 q0 q0 1 0
q1 q1 q1 q1 0 1
Transition Diagram:

7] Design Moore and Mealy machine to convert each occurrence of “100” by”101”.
Solution:
Moore Machine: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={0,1}
Q={q0,q1,q2,q3}
Transition Table:
∑ o/p
0 1
Q
q0 q0 q1 0
q1 q2 q1 1
q2 q3 q1 0
q3 q0 q1 1

Transition Diagram:

Prepared By: Rohini Patil Page 51

 Theory of computation

Mealy machine:
State transition table δ= Output table λ=
∑ ∑
0 1 0 1
Q Q
q0 q0 q1 q0 0 1
q1 q2 q1 q1 0 1
q2 q3 q1 q2 1 1
q3 q0 q1 q3 0 1
Transition Diagram:

8] Design Moore machine to convert each occurrence of “1000” to”1001”.

Solution:
Moore Machine: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={0,1}
Transition Table:

Prepared By: Rohini Patil Page 52

 Theory of computation

∑ 0 1 o/p
Q
0 q0 q0 q1 0

1 q1 q2 q1 1

10 q2 q3 q1 0

100 q3 q4 q1 0

1000 q4 q0 q1 1

Transition Diagram:

9]Design Moore machine to convert each occurrence of “120” to”122”over Σ={0,1,2}

Solution:
Moore Machine: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={0,1,2}
Transition Table:
∑ 0 1 2 o/p
Q
0 q0 q0 q1 q2 0
1 q1 q0 q1 q3 1

2 q2 q0 q1 q2 2

12 q3 q4 q1 q2 2

120 q4 q0 q1 q2 2

Prepared By: Rohini Patil Page 53

 Theory of computation

Transition Diagram:

10] Design Moore machine to count each occurrence of “abb” Σ={a,b}

Solution:
Moore Machine: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={a,b}
∆={a,b}
Transition table:
∑ a b o/p
Q
a q0 q2 q1 ɛ

b q1 q0 q1 ɛ

aa q2 q0 q3 ɛ

aab q3 q0 q1 0

Transition Diagram:

11] Design Mealy machine to find addition of two binary numbers.

Solution: For binary addition input becomes, ∑={(0,0) ,(0,1), (1,0), (1,1) }
∆ ={0,1}

Prepared By: Rohini Patil Page 54

 Theory of computation

Q={q0,q1}
q0 which gives no carry, q1 which gives carry
In qo state In q1 state
0+0 =0 no carry 0+0+carry=1 no carry
0+1=1 no carry 0+1+carry=0 carry
1+0=1 no carry 1+0+carry=0 carry
1+1=0 carry 1+1+carry=1 carry

Transition table:
State transition table δ=
∑
(0,0) (0,1) (1,0) (1,1)
Q
q0 q0 q0 q0 q1
q1 q0 q1 q1 q1

Output table λ=

∑
(0,0) (0,1) (1,0) (1,1)
Q
q0 0 1 1 0
q1 1 0 0 1

Transition Diagram:

12]Design Mealy machine to to o/p even and odd depending on the no of 1’s encountered
are Even and odd over Σ={0,1}
Solution: Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={0,1}
∆={Even,odd}
Q={q0,q1}

Prepared By: Rohini Patil Page 55

 Theory of computation

State transition table δ= Output table λ=

∑ ∑
0 1 0 1
Q Q
q0 q0 q1 q0 Even odd
q1 q1 q0 q1 Odd Even

Transition Diagram:

13] Design Mealy machine to change each occurrence of “abb” to “aba” over Σ={a,b}
Solution:Let M=(Q,∑,∆,δ,λ ,q0) be the required machine.
∑={a,b}
∆={a,b}
Q={q0,q1,q2,q3}
State transition table δ= Output table λ=
∑ ∑
a b a b
Q Q
q0 q0 q2 q0 a b
q1 q0 q1 q1 a b
q2 q0 q3 q2 a a
q3 q0 q1 q3 a b

Transition Diagram:

Prepared By: Rohini Patil Page 56

 Theory of computation

 Equivalence of Moore and Mealy Machines:

It is possible to convert Moore to Mealy machine. In the same way for every mealy machine we
can construct equivalent Moore machine.
 Moore to Mealy Conversion:
Steps:
1. Assign output symbol of each state to all the incoming transitions of that the state.
2. If there is no incoming transition then output symbol of the state can be ignored.
Example: Convert the given Moore machine to Mealy machine

Fig: Moore Machine Fig: Mealy Machine

As we see from the above diagram the output of state q0 is “a”,so we will assign “a” output to
all incoming transitions of q0. Same procedure is repeated for all states.

 Mealy to Moore Conversion

For Every Mealy machine there is an equivalent Moore machine.
Steps:
1. If all incoming transitions to a state have the same output symbol then assign the
output symbol to the state.
2. If incoming transitions to a state are having different output symbols then split the
state as many times as there are output symbols and assign each output symbol to the
new splitted state.
3. If there are no incoming transitions for any state then one of the output symbols can
be assigned to that State
4. If initial state is splitted then one of the splitted state taken as new initial state.

Example: Convert following Mealy machine to Moore machine.

Prepared By: Rohini Patil Page 57

 Theory of computation

Fig: Mealy Machine Fig: Moore Machine

In above diagram we see all incoming transition to state q0 is ‘1’therefore output of q0 is ”1”
Similarly, output of q1 is ”0” and output of state q2 will be “1”.
Now, for q3 state incoming transitions have two different output symbols as “0” and”1”.
Therefore, we will split the state q3 as [q3 0] and [q3 1].The output of state [q3 0] will be “0”
and output of [q3 1] will be “1”.

Example 2: Convert the given Mealy machine to Moore machine.

Fig: Mealy Machine Fig: Moore Machine

In above diagram we see all incoming transition to state q0 is ‘a’ therefore output of q0 is ”a”
Similarly, output of q2 is ”b” and output of state q2 will be “b”.
Now, for q1 state incoming transitions have two different output symbols as “a” and”b”.
Therefore, we will split the state q1 as [q1a] and [q1b].The output of state [q1a] will be “a” and
output of [q1b] will be “b”.

Prepared By: Rohini Patil Page 58

 Theory of computation

Example 3: Convert the given Mealy machine to Moore machine.

In above diagram we see all incoming transition to state q1 is ‘n’ therefore output of q1 is ”n”
Similarly, output of q2 is ”y” and output of state q0 will be “either n or y ”.
Now, for q3 state incoming transitions have two different output symbols as “n” and”y”.
Therefore, we will split the state q3 as [q3n] and [q3y].similarly for q4 it is[q4n] and [q4y].

Difference between Moore and Mealy Machine

Moore Machine Mealy Machine
1. The output depends on only current The output depends on both ,the current state
state of the machine and input.
2. The output symbol is associated with The output symbol is associated with the
the state. transitions.
3. The output mapping is defined as, The output mapping is defined as,
λ: Q  ∆ λ: Q X ∑  ∆
4. If the length of I/p sequence is n, then If the length of I/p sequence is n, then length
length of o/p sequence is n+1 of o/p sequence is also n
5. We can get the output on ɛ We cannot get the output on ɛ
6. Example Example

Applications of Finite Automata:

 It is used in Lexical analysis phase of compiler design.

 It is the base for the formal languages and these formal languages are useful of the
programming languages.

 To prove the correctness of the program.

Prepared By: Rohini Patil Page 59

 Theory of computation

 In analysis and design of digital circuit.

 Used in string matching.

May-2014(CBGS)
1 Differentiate between NFA and DFA. 05
2 Give applications of finite automata 02
3 Compare and contrast Mealy and Moore machine. Design Moore 10
machine to find residue modulo 3 for binary numbers
4 Construct NFA that accepts a set of all strings over {a, b} ending with 10
“abb”. Convert this NFA to equivalent DFA
Dec-2014(CBGS)
1 State and Prove Equivalence of NFA and DFA 05
2 Design DFA to accept the strings over Σ={a,b}that begins with’aa’ but 10
not ends with ‘aa’.
3 Design Moore and Mealy machine to Decrement a binary number 10
May-2014
1 Distinguish between NFA and DFA. 05
2 Design a DFA to check whether a given number is divisible by 4. 08
3 Define NDFA with an example. 02
4 Design Moore machine for the language (0+1)*(00+11) and convert it 10
to Mealy machine.
Dec-2014
1 Design a FSM that check if a given decimal no is even 05
2 What are the steps to convert Moore machine to Mealy machine. 10
Design Moore and Mealy machine to change each occurrence of 100 to
101
May-13
1 Differentiate between Moore and Mealy Machine with proper examples 10
and usage carry out conversions of Moore M/C to Mealy M/C
DEC-13
1 Define with examples Moore and Mealy Machine. 05
2 Design a finite state machine to determine whether a ternary number 10
with base 3 is divisibly by 5.
3 Design Mealy machine for the language (0+1)*(00+11) and convert it 10
to Moore machine.
May-12
1 Compare and contrast Moore and Mealy Machine. 05

Prepared By: Rohini Patil Page 60

 Theory of computation

2 Convert following NFA to DFA. 10

DEC-12
1 Q. 1 What is a finite automaton? Give finite automata accepting 05
(a,b)*(baaa)
2 Design finite state machine to add 2 binary numbers of equal length. 10
3 Differentiate between Moore and Mealy Machine. 05
4 Write short note on applications of FA. 02
MAY-11
1 Differentiate between 10
1. NFA and DFA
2. Moore and Mealy Machine.
2 Find a minimum state finite automata equivalent to following automata- 10
0 1
a b a
b a c
c d b
d* d a
e d f
f g e
g f g
h h d
3 Design Mealy machine for the language (0+1)*(00+11) and convert it 10
to Moore machine.
4 Design DFAto accept following languages over Σ={0,1} 10
L={w|w starts with 0 and has odd length and start with 1 has even
length}
L={Every odd position of w is 1}
DEC-11
1 Design finite state machine to accept exactly two strings baa and ab. 5
2 Convert the following NFA to DFA 5
∑
0 1
Q
p {p,q} p
q {r, s} t
R {p,r} t
s* ø ø

Prepared By: Rohini Patil Page 61

 Theory of computation

t* ø ø

3 Obtain DFA to accept the strings which contains exctly three a’s over ∑ 8
={a, b}
4 Give Moore and Mealy machine to change each occurrence of substring 10
120 to 121 over ∑ ={0, 1, 2}
5 Minimize the following DFA 10
a b
q0 q1 q3
q1 q0 q3
q2 q1 q4
q3* q5 q5
q4 q3 q3
q5* q5 q5

May-10
1 Define DFA and state applications of Finite Automata in brief. 05
2 Obtain DFA to accept strings of a’s and b’s with even no of a’s and 10
even no of b’s.
3 Give Mealy and Moore machine for input from ∑={0,1} if theinput 10
ends in 101, output should be x, if input ends in 110 and output should
be y, otherwise output should be z.
4 Minimize the following DFA, where q0 is start state and q3 and q5 are 10
final states
a b
q0 q1 q3
q1 q0 q3
q2 q1 q4
q3* q5 q5
q4 q3 q3
q5* q5 q5
DEC-10
1 Design Moore and Mealy machine to change each occurrence of 10
substring abb to aba.
2 Design DFA to accept languages 10
Set of all strings with odd number of 1’s followed by even number of
0’s
Set of all strings which begin and end with different letters ∑ ={x, y, z}

Prepared By: Rohini Patil Page 62