Syllabus : Unit – I : Fundamentals and Finite Automata

Strings - Alphabets and languages - Finite state systems – Basic Definitions - Finite Automata -
Deterministic finite automata – Non deterministic finite automata - Equivalence of DFA and NFA -
Equivalence of NFA with and without ε –moves - Minimization of FA - Finite automata with output
– More machines and mealy machines.

Introduction

 Definition of TOC
TOC describes the basic ideas and models underlying computing. TOC
suggests various abstract models of computation, represented mathematically.

 History of Theory of Computation

 1936 Alan Turing invented the Turing machine, and proved that there exists
an unsolvable problem.
 1940’s Stored-program computers were built.
 1943 McCulloch and Pitts invented finite automata.
 1956 Kleene invented regular expressions and proved the equivalence of
regular expression and finite automata
 1956 Chomsky defined Chomsky hierarchy, which organized languages
recognized by different automata into hierarchical classes.
 1959 Rabin and Scott introduced nondeterministic finite automata and proved
its equivalence to (deterministic) finite automata.
 1950’s-1960’s More works on languages, grammars, and compilers
 1965 Hartmantis and Stearns defined time complexity, and Lewis, Hartmantis
and Stearns defined space complexity.
 1971 Cook showed the first NP-complete problem, the satisfiability problem.
 1972 Karp Showed many other NP-complete problems.
 1976 Diffie and Helllman defined Modern Cryptography based on NP-
complete problems.
 1978 Rivest, Shamir and Adelman proposed a public-key encryption scheme,
RSA.

Finite State systems

A finite automaton can also be thought of as the device shown below consisting of a tape
and a control circuit which satisfy the following conditions:
 The tape has the left end and extends to the right without an end.
 The tape is dividing into squares in each of which a symbol can be written prior to the
start of the operation of the automaton.
 The tape has a read only head.
 The head is always at the leftmost square at the beginning of the operation.
 The head moves to the right one square every time it reads a symbol.
It never moves to the left. When it sees no symbol, it stops and the automaton
terminates its operation.
 There is a finite control which determines the state of the automaton and also controls
the movement of the head.

1 / 28
Basic Definitions

 Symbol :
Symbol is a character.
Example : a,b,c,… , 0,1,2,3,….9 and special characters.

 Alphabet :
An alphabet is a finite, nonempty set of symbol. It is denoted by ∑. Example :
a) ∑ = {0,1}, the set of binary alphabet.
b) ∑ = {a,b…......z}, the set of all lowercase letters.
c) ∑ = {+, &,… }, the set of all special characters.

 String or Word :
A string is a finite set sequence of symbols chosen from some alphabets.
Example :
a) 0111010 is a string from the binary alphabet ∑ = {0,1}
b) aabbaacab is a string from the alphabet ∑ = {a,b,c}

 Empty String :
The empty string is the string with zero occurrences of symbols (no symbols). It
is denoted by є.

 Length of String :
The length of a string is number of symbols in the string. It denoted by |w|.

Example :
w = 010110101 from binary alphabet ∑ = {0,1} Length
of a string |w| = 9

2 / 28
 Power of an Alphabet:
 If ∑ is an alphabet, we can express the set of all strings of certain length
from that alphabet by using an exponential notation. It is denoted by ∑k is
the set of strings of length k, each of whose symbols is in ∑.

Example :
∑ = {0,1} has 2 symbols
i) ∑1 = {0,1} ( 21 = 2)
ii) ∑ = {00, 01, 10, 11} ( 22 = 4)
2

iii) ∑3 = {000,001,010,011,100,101,110,111} ( 23 = 8)

 The set of strings over an alphabet ∑ is usually denoted by ∑*.

For instance, ∑* = {0,1}* = {є,0,1,00,01,10,11}
(∑*=∑0∑1∑2……) - with є symbol.

 The set of strings over an alphabet ∑ excluding є is usually denoted by ∑+.

For instance, ∑+ = {0,1}+ = {0,1,00,01,10,11}
...............
(∑+=∑*- {є} or ∑1∑2∑3 )
- without є symbol.

 Concatenation of String
Join the two or more strings. Let x and y be two strings. Concatenation of
strings x and y is appending symbols of y to right end of x.
x = a1a2a3……………an and y = b1b2b3..............................bn
Concatenation of String xy = a1a2a3……an b1b2b3...............bn

Example :
s = ababa and t = cdcddc
Concatenation st = ababacdcddc

 Languages:
If Σ is an alphabet, and L  Σ* then L is a language.
Examples:
o The set of legal English words
o The set of legal C programs
o The set of strings consisting of n 0's followed by n 1's
{ ϵ, 01,0011,000111, …}

 Operations on Languages
 Complementation
Let L be a language over an alphabet Σ. The complementation of L, denoted
byL, is Σ*–L.
 Union
Let L1 and L2 be languages over an alphabet Σ. The union of L1 and L2,
denoted by L1L2, is {x | x is in L1 or L2}.
 Intersection
Let L1 and L2 be languages over an alphabet Σ. The intersection of L1 and L2,
denoted by L1L2, is { x | x is in L1 and L2}.

3 / 28
  Concatenation
Let L1 and L2 be languages over an alphabet Σ. The concatenation of L1 and
L2, denoted by L1L2, is {w1w2| w1 is in L1 and w2 is in L2}.
 Reversal
Let L be a language over an alphabet Σ. The reversal of L, denoted by Lr, is
{wr| w is in L}.
 Kleene’s closure
Let L be a language over an alphabet Σ. The Kleene’s closure of L, denoted by
L*, is {x | for an integer n  0 x = x1 x2 … xn and x1, x2 , …, xn are in L}.
∞
L = U Li
*
(e.g. a* ={,a,aa,aaa,……})
i=0

 Positive Closure
Let L be a language over an alphabet Σ. The closure of L, denoted by L+, is
{ x |for an integer n  1, x = x1x2…xn and x1, x2 , …, xn are in L}
∞
L = U Li
+
(e.g. a* ={a,aa,aaa,……})
i=1

Finite Automata
Automaton is an abstract computing device. It is a mathematical model of a system,
with discrete inputs, outputs, states and set of transitions from state to state that occurs on
input symbols from alphabet Σ.
 It representations:
o Graphical (Transition Diagram or Transition Table)
o Tabular (Transition Table)
o Mathematical (Transition Function or Mapping Function)
 Formal Definition of Finite Automata
A finite automaton is a 5-tuples; they are M=(Q, Σ, δ, q0, F)
where
Q is a finite set called the states
Σ is a finite set called the alphabet
δ : Q ×Σ → Q is the transition function
q0 ∈ Q is the start state also called initial state
F ⊆ Q is the set of accept states, also called the final states

 Transition Diagram (Transition graph)

It is a directed graph associated with the vertices of the graph corresponds to
the states of the finite automata. (or) It is a 5-tuple graph used state and edges
the transitions from one state to other state.
represent 1
Example: 0 1

0 qq22
q0 q1
Start or Initial State Final or Accepting State
4 / 28
 Transition Table.
It is the tabular representation of the DFA. For a transition table the transition
function is used.
Example:

Input
States 0 1
{q0} {q1} {q0}
{q1} - {q2}
*{q2} - -
 Transition Function.
- The mapping function or transition function denoted by δ.
- Two parameters are passed to this transition function: (i) current state and
(ii) input symbol.
- The transition function returns a state which can be called as next
state. δ ( current_state, current_input_symbol ) = next_state
Example:
δ ( q0, a ) = q1

 Computation of a Finite Automaton

o The automaton receives the input symbols one by one from left to right.
o After reading each symbol, M1 moves from one state to another along the
transition that has that symbol as its label.
o When M1 reads the last symbol of the input it produces the output: accept if
M1 is in an accept state, or reject if M1 is not in an accept state.

 Applications
o It plays an important role in complier design.
o In switching theory and design and analysis of digital circuits automata
theory is applied.
o Design and analysis of complex software and hardware systems.
o To prove the correctness of the program automata theory is used.
o To design finite state machines such as Moore and mealy machines.
o It is base for the formal languages and these formal languages are useful of
the programming languages.

 Types of Finite Automata

o Finite Automata without output
o Deterministic Finite Automata (DFA)
o Non-Deterministic Finite Automata (NFA or NDFA)
o Non-Deterministic Finite Automata with ε move (ε-NFA or ε-NDFA)
o Finite Automata with output
o Moore Machine
o Mealy Machine

5 / 28
Deterministic Finite Automata (DFA)

Deterministic Finite Automaton is a FA in which there is only one path for a specific
input from current state to next state. There is a unique transition on each input symbol.

 Formal Definition of Deterministic Finite Automata

A finite automaton is a 5-tuples; they are M=(Q, Σ, δ, q0, F)
where
Q is a finite set called the states
Σ is a finite set called the alphabet
δ : Q ×Σ → Q is the transition function
q0 ∈ Q is the start state also called initial state
F ⊆ Q is the set of accept states, also called the final states

0
1 qS
21
S0 1 1

0
S2
0

Non-Deterministic Finite Automata (NDFA or NFA)

Non-Deterministic Finite Automaton is a FA in which there many paths for a

specific input from current state to next state.

 Formal Definition of Non-Deterministic Finite Automata

A finite automaton is a 5-tuples; they are M=(Q, Σ, δ, q0, F)
where
Q is a finite set called the states
Σ is a finite set called the alphabet
δ : Q ×Σ → 2Q is the transition function
q0 ∈ Q is the start state also called initial state
F ⊆ Q is the set of accept states, also called the final states
1
0 1

q0 1
q1 qq22
0

6 / 28
Finite Automaton with ε- moves
The finite automata is called NFA when there exists many paths for a specific input
or ε from current state to next state. The  is a character used to indicate null string.

 Formal Definition of Non-Deterministic Finite Automata

A finite automaton is a 5-tuples; they are M=(Q, Σ, δ, q0, F)
where
Q is a finite set called the states
Σ is a finite set called the alphabet
δ : Q ×(Σ  {ε}) → 2Q is the transition function q0
∈ Q is the start state also called initial state
F ⊆ Q is the set of accept states, also called the final states
1
0 1


q0  qq22
q1

Differentiate DFA and NFA

Sl. No DFA NFA
DFA is Deterministic Finite NFA is Non-Deterministic Finite
1.
Automata Automata
For given state, on a given input For given state, on a given input
2. we reach to deterministic and we reach to more than one state.
unique state.
DFA is a subset of NFA Need to convert NFA to DFA in
3.
the design of complier.
δ : Q ×Σ → Q δ : Q ×Σ → 2Q
4.
Example: δ(q0, a) = {q1} Example : δ(q0, a) = {q1, q2}

Problems for Finite Automata

1. Design FA which accepts odd number of 1’s and any number of 0’s.

0
1 qS
21
S0 1 1

0
S2
0

2. Design FA to accept the string that always ends with 00.

1 0

0 0
q0 q1 qq
1
22
1
7 / 28
 3. Design FA to check whether given unary number is divisible by three.

1 1 1 q
q0 q1 q1 2
q2
1
4. Design FA to check whether given binary number is divisible by three.
0
0 qS
21
S0 1 1
0
1 0
S2 S3
0

5. Obtain the  closure of states q0 and q1 in the following NFA with  transition.
a b c


q0 q1 q2
Solution:
 - CLOSURE {q0} = {q0, q1,q2}
 - CLOSURE {q1} = {q1,q2}

6. Obtain  closure of each state in the following NFA with  move.

2
0 1

 
q0 q1
qq
Solution:
 - CLOSURE {q0} = {q0, q1,q2}
 - CLOSURE {q1} = {q1,q2}
 - CLOSURE {q2} = {q2}

Tutorial:

7. Design Finite Automata which accepts the only 0010 over the input Σ = {0, 1}.
8. Design Finite Automata which checks whether given binary number is even
or odd over the input Σ = {0, 1}.
9. Design Finite Automata which accepts only those strings which starts with
‘a’ and end with ‘b’ over the input Σ = {a, b}.

8 / 28
 10. Design a DFA to accept the language L = {w | w has both an even number of
0’s and an even number of 1’s.
11. Design a DFA to accept the language L = {w | w has both an odd number of
0’s and an odd number of 1’s.
12. Obtain  closure of each state in the following NFA with  move.
b
a, b

ε ε a, b
q0 q1 qq
22

Equivalence of NFA and DFA

For every NFA, there exists an equivalent DFA.

Theorem:

For every NFA, there exists a DFA which simulates the behavior of NFA. If L is the set
accepted by NFA, then there exists a DFA which also accepts L.
Or
Let L be a set accepted by NFA (L(M)), then there exists a DFA that accepts (L(Mʹ)).

Proof:

Let M = (Q, Σ, δ, q0, F) be an NFA for language L, then define DFA Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ).
 The states of Mʹ are all the subset of M.
 The elements in Qʹ will be denoted by [q1, q2, q3, … , qi] and the elements in Q are
denoted by {q1, q2, q3, … , qi}.
 Initial state of NFA is q0, and also an initial state of DFA is q0ʹ =[q0].
 we define
δʹ ([q1, q2, q3, …, qi],a) = [p1, p2, p3, …, pi]
if only if
δ({q1, q2, q3, …, qi},a) = {p1, p2, p3, …, pi}

This means that whenever in NFA, at the current state {q 1, q2, q3, …, qi} if we
get input ‘a’ and it goes to the next states {p 1, p2, p3, …, pi} then while constructing
DFA for it the current state is assumed to be [q1, q2, q3, …, qi]. At this state, the input
is ‘a’ and it goes to the next state is assumed to be [p 1, p2, p3, …, pi]. On applying
transition function on each of the state’s q 1, q2, q3, …, qi the new state may be any of
the state’s from p1, p2, p3, …, pi.

Theorem can be proved with the induction method by assuming length of input string ‘x’.

δʹ(q0ʹ, x) = [q1, q2, q3, …, qi]

if only if
δ(q0, x) = {q1, q2, q3, …, qi}

9 / 28
Basis method:
If the input string length is 0. ie. |x|=0 where x = {ε}, then q0ʹ = [q0].

Induction method:

If we assume that the hypothesis is true for the length of input string is less than or
equal to ‘m’. Then if ‘xa’ is a length of string is m+1. Hence the transition function (δʹ) could
be written as,

δʹ (q0ʹ, xa) = δʹ (δʹ (q0ʹ, x),a)

By induction hypothesis,

δʹ(q0ʹ, x) = [p1, p2, p3, …, pi]

if only if
δ(q0, x) = {p1, p2, p3, …, pi}

By definition of δʹ

δʹ( [p1, p2, p3, …, pi], a) = [r1, r2, r3, …, ri]

if only if
δ({p1, p2, p3, …, pi}, a) = {r1, r2, r3, …, ri}
Thus,
δʹ (q0ʹ, xa) = [r1, r2, r3, …, ri]
if only if
δ (q0, xa) = {r1, r2, r3, …, ri}

Shown by induction hypothesis,

L(M) = L(Mʹ)

Extended Transition Function (δʹʹ or δ^)

This is used to represent transition functions with a string of input symbols ‘w’ and returns a
set of states. It is represented by δʹʹ or δ^

Suppose w = xa
δ (q, x) = {p1, p2, p3, …, pk}
then
∞
U δʹʹ(pi,a) = {r1, r2, r3, …, rm}
i=0

δʹʹ(pi, xa) = δʹʹ( δ(q,x) a))

10 / 28
Example Problems for Converting NFA into DFA
1. Obtain the DFA equivalent to the following NFA.

0, 1

0 1 qq
q0 q1
22
Solution :
The transition table for given NFA can be drawn as follows
Input
States 0 1
{q0} {q0}{q1} {q0}
{q1} - {q2}
*{q2} - -

Let the DFA Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ) then, transition function (δʹ) will be computed as,

δʹ([q0], 0) = [q0, q1] - a new state - A

δʹ([q0], 1) = [q0]
δʹ([q1], 0) = -
δʹ([q1], 1) = [q2]
δʹ([q2], 0) = -
δʹ([q2], 1) = -
δʹ([qo,q1],0) = [q0,q1]
δʹ([qo,q1],1) = [q0,q2] a new state - B
δʹ([qo,q2],0) = [q0,q1]
δʹ([qo,q2],0) = [q0]

The transition table for DFA

Input
States
0 1
[q0] [q0, q1] [q0]
[q1] - [q2]
*[q2] - -
[q0, q1] [q0, q1] [q0, q2]
*[q0, q2] [q0, q1] [q0]
The transition diagram for DFA
1 0
1 qq
0 1 q1
q0 A q 221
B2
0
1

11 / 28
2. Let M = ({q0, q1}, {0,1}, δ, q0, {q1}) be NFA. Where δ (q0, 0) = {q0, q1},
δ (q0, 1) = {q1}, δ (q1, 0) = {}, δ (q1, 1) = {q0, q1}. Construct its equivalent DFA.

Solution :
The transition table for NFA
Input
States 0 1
{q0} {q0}{q1} {q1}
*{q1}  {q0}{q1}
The transition diagram for NFA
1
0
0, 1
q0 qq
21
1

Let the DFA Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ) then, transition function (δʹ) will be computed as,

δʹ ([q0], 0) = [q0, q1] -a new state A

δʹ([q0], 1) = [q1]
δʹ([q1], 0) = 
δʹ([q1], 1) = [q0]
δʹ([q0,q1],0) = [q0,q1]
δʹ([qo,q1],1) = [q0,q1]

The transition table for DFA

Input
States
0 1
[q0] [q0, q1] [q1]
*[q1]  [q0]
*[q0, q1] [q0, q1] [q0, q1]

The transition diagram for DFA

1

1
q0 q1

[q0,q1] 0, 1

12 / 28
Tutorial:

3. Obtain the DFA equivalent to the following NFA.

a, b
a, b

b a a, b
q0 q1 qq
22
4. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be NFA. Where δ (q0, 0) = {q0, q1},
δ (q0, 1) = {q1}, δ (q1, 0) = {q2,q3}, δ (q1, 1) = {q0, q1}, δ (q2, 0) = {q2},
δ (q2, 1) = {q0, q3}, δ (q3, 0) = {q3}, δ (q3, 1) = {q2, q3}, Construct its equivalent
DFA.

Equivalence of NDFA’s with and without ε-moves

Theorem:

If L is accepted by NFA with ε-moves, then there exists L which is accepted by NFA
without ε-moves.

Proof:
Let M = (Q, Σ, δ, q0, F) be an NFA with ε-moves for language L, then define NFA without
ε-moves Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ).
 The elements in Qʹ will be denoted by [q1, q2, q3, … , qi] and the elements in Q are
denoted by {q1, q2, q3, … , qi}.
 Initial state of NFA with ε-moves is q0, and also an initial state of NFA without ε-moves
is q0ʹ =[q0].
 Fʹ =
 δʹ can be denoted by δʹʹ with some input.

Basis:
|X| = 1, where X is a symbol ‘a’.
δʹ(q0,a) = δʹʹ(q0,a)
Induction:
|X| > 1, Let X = wa
δʹ(q0,wa) = δʹ( δʹʹ(q0,w),a)
By induction hypothesis,
δʹ(q0,w) = δʹʹ(q0,w) = p
Now we will show that
δʹ(p,a) = δ(q0,wa)
But,
δʹ(p,a) = δʹ(q,a) = δʹʹ(q,a) as p = δʹʹ(q0,w)
We have
δʹʹ(q,a) = δʹʹ(q0,wa)
Thus by definition of δʹʹ
δʹ(q0,wa) = δʹʹ(q0,wa)

13 / 28
Example Problems for Converting NFA with  into NFA without 

1. Construct NFA without  from NFA with .

2
0 1

 
q0 q1
qq

Solution:
Find the ε – closure function of all states:
ε – closure (q0) = {q0, q1, q2}
ε – closure (q1) = {q1, q2}
ε – closure (q0)
ε – closure (q2) = {q2}
= { q0,q1,q2}
Compute δʹ function:
δʹ(q0,0) = δʹʹ (q0,0) = ε – closure (δ(δʹ(q0,ε),0))
= ε – closure (δ({q0,q1,q2},0))
= ε – closure (q0) = {q0,q1,q2}
δʹ(q0,1) = δʹʹ (q0,1) = ε – closure (δ(δʹ(q0,ε),1))
= ε – closure (δ({q0,q1,q2},1))
= ε – closure (q1) = {q1,q2}
δʹ(q0,2) = δʹʹ (q0,2) = ε – closure (δ(δʹ(q0,ε),2))
= ε – closure (δ({q0,q1,q2},2))
= ε – closure (q2) = {q2}
δʹ(q1,0) = δʹʹ (q1,0) = ε – closure (δ(δʹ(q1,ε),0))
= ε – closure (δ({q1,q2},0))
= ε – closure () = {}
δʹ(q1,1) = δʹʹ (q1,1) = ε – closure (δ(δʹ(q1,ε),1))
= ε – closure (δ({q1,q2},1))
= ε – closure (q1) = {q1,q2}
δʹ(q1,2) = δʹʹ (q1,2) = ε – closure (δ(δʹ(q1,ε),2))
= ε – closure (δ({q1,q2},2))
= ε – closure (q2) = {q2}
δʹ(q2,0) = δʹʹ (q2,0) = ε – closure (δ(δʹ(q2,ε),0))
= ε – closure (δ({q2},0))
= ε – closure () = {}
δʹ(q2,1) = δʹʹ (q2,1) = ε – closure (δ(δʹ(q2,ε),1))
= ε – closure (δ({q2},1))
= ε – closure () = {}
δʹ(q2,2) = δʹʹ (q2,2) = ε – closure (δ(δʹ(q2,ε),2))
= ε – closure (δ({q2},2))
= ε – closure (q2) = {q2}

14 / 28
 The transition table for NFA
Input
States 0 1 2
q0 {q0,q1,q2} {q1,q2} {q2}
q1 {} {q1,q2} {q2}
*q2 {} {} {q2}
The transition diagram for NFA
2
1
0
0,1 1,2
q0 q1 q2
q2
0,1,2

2. Construct NFA without  from NFA with .

0 1

ε
qq qq
20
21
Solution:
Find the ε – closure function of all states:
ε – closure (q0) = {q0, q1}
ε – closure (q1) = {q1}

Compute δʹ function:
δʹ(q0,0) = δʹʹ (q0,0) = ε – closure (δ(δʹ(q0,ε),0))
= ε – closure (δ({q0,q1},0))
= ε – closure (q0) = {q0,q1}
δʹ(q0,1) = δʹʹ (q0,1) = ε – closure (δ(δʹ(q0,ε),1))
= ε – closure (δ({q0,q1},1))
= ε – closure (q1) = {q1}
δʹ(q1,0) = δʹʹ (q1,0) = ε – closure (δ(δʹ(q1,ε),0))
= ε – closure (δ({q1},0))
= ε – closure () = {}
δʹ(q1,1) = δʹʹ (q1,1) = ε – closure (δ(δʹ(q1,ε),1))
= ε – closure (δ({q1},1))
= ε – closure (q1) = {q1}

The transition table for NFA

Input
States
0 1
*q0 {q0,q1} {q1}
*q1 {} {q1}

15 / 28
 The transition diagram for NFA

0 1

0,1
qq qq
20
Tutorial: 21

1. Obtain the NFA equivalent to the following NFA with -move.

b
a, b

ε ε a, b
q0 q1 qq
22
2. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be -NFA.
Where δ (q0, 0) = {q0, q1}, δ (q0, 1) = {q1}, δ (q1, 0) = {q2,q3}, δ (q1, ε) = {q1},
δ (q1, 1) = {q0, q1}, δ (q2, 0) = {q2}, δ (q2, ε) = {q3}, δ (q2, 1) = {q0, q3,},
δ (q3, 0) = {q3}, δ (q3, 1) = {q2, q3}, δ (q3, ε) = {q0}. Construct its equivalent
NFA.

Example Problems for Converting NFA with -move into DFA

1. Construct DFA from the following -NFA.

b
a, b

ε ε a, b
q0 q1 qq
22
Solution:
ε – closure (q0) = {q0, q1, q2}  A new state in DFA

ε – closure (δ (A, a)) = ε – closure (q0,q2)

= {q0, q1, q2}  A
ε – closure (δ (A, b)) = ε – closure (q0,q1,q2)
= {q0, q1, q2}  A

The transition table for DFA

Input
States a,b
A b
*A A A

The transition diagram for DFA qA2

16 / 28
 2. Construct DFA from the following -NFA.
0
1 0

r
q
ε
0 ε

1
p ε ε

qs
0 2

Solution:
ε – closure (p) = {p,q,r}  A new state in DFA

ε – closure (δ (A, 0)) = ε – closure (p,r) = ε – closure (p)  ε – closure (r)

= {p,q,r}  {r,s} = {p,q,r,s}  B new state in DFA

ε – closure (δ (A, 1)) = ε – closure (q,s) = ε – closure (q)  ε – closure (s)

= {q,r}  {p,q,r,s} = {p,q,r,s}  B

ε – closure (δ (B, 0)) = ε – closure (p,r) = ε – closure (p)  ε – closure (r)

= {p,q,r}  {r,s} = {p,q,r,s}  B

ε – closure (δ (B, 1)) = ε – closure (q,s) = ε – closure (q)  ε – closure (s)

= {q,r}  {p,q,r,s} = {p,q,r,s}  B

The transition table for DFA

Input
States
0 1
A B B
*B B B

The transition diagram for DFA

0,1

0,1
A q2
B

17 / 28
Tutorial:

1. Obtain the DFA equivalent to the following NFA with -move.

2
0 1

 
q0 q1
qq

2. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be -NFA.

Where δ (q0, 0) = {q0, q1}, δ (q0, 1) = {q1}, δ (q1, 0) = {q2,q3}, δ (q1, ε) = {q1},
δ (q1, 1) = {q0, q1}, δ (q2, 0) = {q2}, δ (q2, ε) = {q3}, δ (q2, 1) = {q0, q3,},
δ (q3, 0) = {q3}, δ (q3, 1) = {q2, q3}, δ (q3, ε) = {q0}. Construct its equivalent
DFA.

Minimization of DFA
 DFA minimization stands for converting a given DFA to its equivalent DFA
with minimum number of states.
 Suppose there is a DFA M = (Q, ∑, q0, δ, F) which recognizes a language L. Then
the minimized DFA M = (Q’, ∑, q0, δ’, F’) can be constructed for language L as:

1. We will divide Q (set of states) into two sets. One set will contain all final
states and other set will contain non-final states. This partition is called P0.
2. Initialize k = 1
3. Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, we will take all
possible pair of states. If two states of a set are distinguishable, we will split the
sets into different sets in Pk.
4. Stop when Pk = Pk-1 (No change in partition)
5. All states of one set are merged into one. No. of states in minimized DFA will
be equal to no. of sets in Pk.

Example:
Consider the following DFA into minimized DFA.

18 / 28
Solution:

Transition Table for DFA

Inputs
States 0 1
q0 q3 q1
*q1 q2 q5
*q2 q2 q5
q3 q0 q4
*q4 q2 q5
q5 q5 q5

Step 1: Divide into two sets. One set is containing final states and other set
containing non-final states.

Inputs Partition
States 0 1 (P0)
q0 q3 q1
q3 q0 q4 Non-Final
q5 q5 q5 States
*q1 q2 q5
*q2 q2 q5 Final States
*q4 q2 q5

Step 2: To calculate P1, we will check whether sets of partition P0 can be partitioned or
not:

For set { q1, q2, q4 } :

 δ ( q1, 0 ) = δ ( q2, 0 ) = q2 and δ ( q1, 1 ) = δ ( q2, 1 ) = q5, So q1 and q2 are
not distinguishable.
 Similarly, δ ( q1, 0 ) = δ ( q4, 0 ) = q2 and δ ( q1, 1 ) = δ ( q4, 1 ) = q5, So q1
and q4 are not distinguishable.
 So, q2 and q4 are not distinguishable. So, {q1, q2, q4} set will not be
partitioned in P1.

Inputs Partition
States 0 1 (P0)
q0 q3 q1
q3 q0 q4 Non-Final
q5 q5 q5 States
*q1 q2 q5
*q2 q2 q5 Final States
*q4 q2 q5

19 / 28
 Step 3: Remove q2 and q4 row from the table and replace q2 and q4 into q1 where
however present in the table.
Inputs Partition
States 0 1 (P0)
q0 q3 q1
q3 q0 q4 q1 Non-Final
q5 q5 q5 States
Final
*q1 q1 q5
States

Step
4:  δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0 - Moves of q0 and q3 on input symbol 0
are q3 and q0 respectively which are in same set in partition P0.
 δ ( q0, 1) = δ ( q3, 1 ) = q1 - Moves of q0 and q3 on input symbol 1 is q1
which are in same set in partition P0.
 So, q0 and q3 are not distinguishable.

Step 5: Remove q3 row from the table and replace q3 into q0 where however present in the
table.

Inputs Partition
States 0 1 (P0)
q0 q3 q0 q1
q3 q0 q1 Non-Final
q5 q5 q5 States
Final
*q1 q1 q5
States

Step 6: Final Transition Table for DFA (no more not distinguishable)

Inputs Partition
States 0 1 (P0)
q0 q0 q1 Non-Final
q5 q5 q5 States
Final
*q1 q1 q5
States

Step 7: Transition Diagram for minimized DFA

0,1
0 0

1 1
q0 qq q5
21

20 / 28
Tutorial:

1. Consider the following DFA into minimized DFA.

2. Consider the following DFA into minimized DFA.

Finite automata with Output

 Finite automata may have outputs corresponding to each transition. There are two model
or machine for finite automata with output.

Finite Automata
with Output

Mealy Machine Moore Machine

Mealy Machine

 A Mealy Machine is an FSM whose output depends on the present state as well as
the present input.
 The value of the output function z(t) depends only on the present state q(t) and
present input λ (t), i.e. z(t) = λ (q(t), x(t))
 The length of output for a mealy machine is equal to the length of input. If input string ,
the output string is also .

21 / 28
 It can be described by a 6 tuples M = (Q, ∑, Δ, δ, λ, q0)
where
 Q is a finite set of states.
 ∑ is a finite set of input symbols
 Δ is a finite set of output symbols
 δ is the input transition function where δ: Q × ∑ → Q
 λ is the output transition function where λ : Q × ∑ → Δ
 q0 is the initial state

 Transition table of mealy machine:

Input = 0 Input = 1
Present State
Next State Output Next State Output

q0 q1 0 q2 0

q1 q1 0 q2 1

q2 q1 1 q2 0

 Transition diagram of mealy machine:

Moore Machine

 Moore machines are FSM whose output depends on the present state as well as the
previous state.
 The value of the output function z(t) depends only on the present state q(t) and
independent of the current input x(t), i.e. z(t) = λ (q(t))
 The length of output for a moore machine is greater than input by 1. If input string , the
output string is λΔ(q(t)).
=
 It can be described by a 6 tuples M = (Q, ∑, Δ, δ, λ, q0)
where
 Q is a finite set of states.
 ∑ is a finite set of input symbols
 Δ is a finite set of output symbols
 δ is the input transition function where δ: Q × ∑ → Q
 λ is the output transition function where λ : Q → Δ
 q0 is the initial state

22 / 28
  Transition table of moore machine:

Next State
Present State Output
Input = Input =
0 1

q0 q1 q2 0

q1 q1 q3 0

q2 q4 q2 0

q3 q4 q2 1

q4 q1 q3 1

 Transition diagram of moore machine:

Mealy Machine vs. Moore Machine

Mealy Machine Moore Machine

Output depends both upon the present state andOutput depends only upon the present state.
the present input

Generally, it has fewer states than Moore Generally, it has more states than Mealy
Machine. Machine.

The value of the output function is a functionThe value of the output function is a function of
of the transitions and the changes, when the the current state and the changes at the clock
input logic on the present state is done. edges, whenever state changes occur.

Mealy machines react faster to inputs. They In Moore machines, more logic is required to
generally react in the same clock cycle. decode the outputs resulting in more circuit
delays. They generally react one clock cycle
later.

23 / 28
Transforming Mealy Machine into Moore Machine

 Transform Mealy Machine into Moore Machine for the given input string and the output
string as same (except for the first symbol).
 Algorithm:
 Step 1: Look into the next state column for any state (example q0,q1, …. qi)
and determine the number of different outputs associated with qi in that column
(output column values are same or different).
 Step 2: qi into several different states. The number of such states being equal
to the number of outputs associated with qi.
 Step 3: qi replaced by qi0 for output 0 and qi1 for output 1
 Step 4: Convert Mealy Structure to Moore Structure
 Step 5: Add new start state with output 0 and next states same as the next states
of first state.

 Example:
Consider the Mealy machine described by the transition table given below. To
construct a Moore machine, this is equivalent to mealy machine.

a=0 a=1
Present State
Next State Output Next State Output

q1 q3 0 q2 0

q2 q1 1 q4 0

q3 q2 1 q1 1

q4 q4 1 q3 0

Solution:
Step 1: Look into the next state column for any state (example q0,q1, …. qi) and
determine the number of different outputs associated with qi in that column (output column
values are same or different).

Determine same or
a=0 a=1 different output
Present State
Next State Output Next State Output

q1 q3 0 q2 0 same

q2 q1 1 q4 0 different

q3 q2 1 q1 1 same

q4 q4 1 q3 0 different

24 / 28
 Step 2: q2 split into q20 and q21 states. Similarly q4 split into q40 and q41.

a=0 a=1
Present State
Next State Output Next State Output

q1 q3 0 q2 0

q20
q2 q1 1 q4 0
q21

q3 q2 1 q1 1

q40
q4 q4 1 q3 0
q41

a=0 a=1
Present State
Next State Output Next State Output

q1 q3 0 q2 0

q20 q1 1 q4 0

q21 q1 1 q4 0

q3 q2 1 q1 1

q40 q4 1 q3 0

q41 q4 1 q3 0

Step 3: q2 replaced by q20 for output 0 and q21 for output 1, similarly q4 replaced by q40
for output 0 and q41 for output 1

a=0 a=1
Present State
Next State Output Next State Output

q1 q3 0 q20 0

q20 q1 1 q40 0

q21 q1 1 q40 0

q3 q21 1 q1 1

q40 q41 1 q3 0

q41 q41 1 q3 0

25 / 28
Step 4: Convert Mealy Structure to Moore Structure

Next State
Present State Output
a=0 a=1

q1 q3 q20 1

q20 q1 q40 0

q21 q1 q40 1

q3 q21 q1 0

q40 q41 q3 0

q41 q41 q3 1

Step 5: Add new start state with output 0 and next states same as the next states of first state.

Next State
Present State Output
a=0 a=1

q0 q3 q20 0

q1 q3 q20 1

q20 q1 q40 0

q21 q1 q40 1

q3 q21 q1 0

q40 q41 q3 0

q41 q41 q3 1

Transition Diagram for Moore Machine

0

0 q3/ 1
0
q41/
0 1 1
q0/ 0 1
0 1
q1/ q21/
1 1
1
1
0 1 0
q20/
0 q40/
0
1

26 / 28
Transforming Moore Machine into Mealy Machine
 Transform Mealy Machine into Moore Machine for the given input string and the output
string as same.
 Algorithm:
 Step 1: Remove output column from moore table and add output column to
mealy table
 Step 2: Fill the output column from moore table.

Example:
Consider the Moore machine described by the transition diagram given below. To
construct a Mealy machine, which is equivalent to moore machine.
1
q3/
1
0
1
q0/ 0
0
0
0 q2/
0
1
q1/ 1
1

Transition Table for Moore Machine

Next State
Present State Output
a=0 a=1

q0 q3 q1 0

q1 q1 q2 1

q2 q2 q3 0

q3 q3 q0 1

Solution:
Step 1: Remove output column from moore table and add output column to mealy table
Transition Table for Mealy:
a=0 a=1
Present State
Next State Output Next State Output

q0 q3 1 q1 1

q1 q1 1 q2 0

q2 q2 0 q3 1

q3 q3 1 q0 0

27 / 28
Transition Diagram for Mealy:
0/1

0/1 q3

q0
1/1 0/0
1/0
0/1 q2
1/1
q1 1/0

Tutorial Problems:
1. Construct the moore machine from the given mealy machine.

2. Construct the moore machine from the given mealy machine.

28 / 28