Ajay Kumar Garg Engineering College, Ghaziabad

Department of Computer Science & Engineering

Session 2024-2025
Theory of Automata and Formal Languages
(BCS402)

Unit: I Finite Automata

B. Tech (IT) Vibha Srivastava

4th Semester (Assistant Professor, CSE)

1
 Syllabus

UNIT-1
Basic Concepts and Automata Theory: Introduction to Theory of
Computation- Automata, Computability and Complexity, Alphabet,
Symbol, String, Formal Languages,
Deterministic Finite Automaton (DFA)- Definition, Representation,
Acceptability of a String and Language,
Non Deterministic Finite Automaton (NFA), Equivalence of DFA and
NFA, NFA with ε-Transition, Equivalence of NFA’s with and without
ε-Transition,
Finite Automata with output- Moore Machine, Mealy Machine,
Equivalence of Moore and Mealy Machine,
Minimization of Finite Automata,
Myhill-Nerode Theorem, Simulation of DFA and NFA

05/02/2025 2
 UNIT-1

05/02/2025 3
 Finite Automata

Objective of the Topic

The objective of the topic is to make the student able to:
• Understand the requirement of finite automata.
• Implement Finite automata
• Realize the expressive power of Ɛ- NFA, NFA and DFA
• Minimize the FA

4
 Introduction to Automata

• Automaton is the system that performs some function without

human intervention.
• The plural of Automaton is Automata.

• Automata theory is the study of abstract computational machines

and the computational problems that can be solved using these
machines
• Abstract machine are (simplified) mathematical models of real
computations.

5
 Introduction to Automata

Temporary Memory

Automaton

Input CPU Output

Program Memory

05/02/2025 6
 Introduction to Automata

Compute f(x)=x2+3? Temporary Memory

y= 5*5
f(x)=25+3

Output
Input
X=5
CPU f(x)=28

Program Memory
y=x*x
f(x)=y+3
05/02/2025 7
 Introduction to Automata
Why do we need abstract models?
ITCH
SW

BATTERY

input: switch
output: light bulb
actions: flip
switch
states: on, off
05/02/2025 8
 Introduction to Automata
A simple “computer”
ITCH
SW

BATTERY start off on

input: switch
output: light bulb bulb is on if and only
if there was an odd
actions: f for “flip number of flips
switch”
states: on, off
05/02/2025 9
 Introduction to Automata
Basic Concept
– Every automaton consists of some
essential features as in real Input Tape
computers.
It has a mechanism for reading input.
i.e. Input Tape
 The automaton can produce
Finite
output of some form.
Control
 If the output is Binary (accept or
reject) - Accepter.
 Output sequence in response to an
input sequence- Transducer
The automaton may have a Output Temp
Storage
temporary storage
The most important feature of the
automaton is its control unit.
05/02/2025 10
 Different Types of Automata
finite automata Devices with a finite amount of
memory.
Used to recognizing or string
matching.
push-down Devices with infinite memory that
automata can be accessed in a restricted way.
Used to model parsers, etc.

Turing Devices with infinite memory.

Machines Used to model any computer.

Linear Bounded Infinite memory, but bounded

Automata running time.
(time-bounded Used to model any computer
Turing program that runs in a “reasonable”
 Common terms used in Automata

Alphabet
An alphabet is a finite, non-empty set of symbols.
It is represented by ∑.
Ex:
∑={0,1} is binary alphabet.
∑={0,1,2,3,4,5,6,7,8,9} is decimal alphabet.
∑={a,b,c,…..,z} is lower-case alphabet.

05/02/2025 12
 Common terms used in Automata

Strings/Words
A string or word is a finite sequence of symbols over ∑.
Ex:
w = 10110 is a string over ∑={0,1}.

05/02/2025 13
 Common terms used in Automata

Length of a string
or
Power of ∑
∑k is the set of strings of length k (|w|=k).
Ex:
If ∑={a,b} then
∑0= {Ɛ} , called Epsilon.
∑1 = {a,b}
∑2 = {aa,ab,ba,bb}

05/02/2025 14
 Common terms used in Automata

Reverse of a string
Reverse of a string, w is represented as wR.
Ex:
If w=xyz then wR =zyx.

Substrings of a string
If w=xyz then its substrings are:
Ɛ, x, y, z, xy, yz, zx, xyz

05/02/2025 15
 Common terms used in Automata

Prefix of a string
If w=xyz then its prefixes are:
Ɛ, x, xy, xyz

Suffix of a string
If w=xyz then its suffixes are:
Ɛ, z, yz, xyz

05/02/2025 16
 Common terms used in Automata

Languages
A set of strings, over ∑, is called a language.
Ex:
L1=[w={0,1}*| w has equal number of 0’s and 1’s]
L1={01,10,0011,0101,0110,1010,1001,1100,……}
L2=[w={a,b}*| |w|3]
L2={Ɛ,0,1,00,01,10,11,000,001,010,011,100,101,1
10,111}

05/02/2025 17
 Common terms used in Automata

Kleene closure
Kleene closure represented as ∑*, is set of strings of all
possible length.

∑*=∑0 ∑1 ∑2 ∑3……….

Ex:
If ∑ ={a,b} then
∑*={Ɛ, a,b,aa,ab,ba,bb,aaa,aab,………..}

05/02/2025 18
 Common terms used in Automata

Positive closure
Positive closure represented as ∑+, is set of strings of all
possible length.
∑+=∑1 ∑2 ∑3……….

∑*= ∑0 ∑+
Ex:
If ∑ ={a,b} then
∑+={a,b,aa,ab,ba,bb,aaa,aab,………..}

05/02/2025 19
 Finite Automata

• Finite Automata: It is a mathematical model that works for several

computer algorithms. It is called finite because it works on Finite set
of Input symbols with Finite number of States and gives output in
finite times.

a b Magnetic
b tape
a b a a

Reading Head

Output
Finite Control

05/02/2025 20
 Applications of Automata

Applications of Finite Automata

• String Matching
• Lexical Analysis
• Design and Analysis of Digital Circuits

05/02/2025 21
 Finite Automata

Finite Automata

Deterministic Finite Non-deterministic

Automata (DFA) Finite Automata (NFA)

05/02/2025 22
 DFA

For a DFA the machine moves to a particular unique state from a given
state and given input that is why it is called Deterministic. As the
number of states in DFA are Finite it is called Deterministic Finite
Automata.

a q1

q0
b
q2

05/02/2025 23
 Deterministic Finite Automata

• A deterministic finite automaton (DFA) is a 5-

tuple (Q, S, d, q0, F) where
– Q is a finite set of states
– S is finite set of alphabet
– d: Q × S → Q is a transition function
– q0 Î Q is the initial state
– F Í Q is a set of accepting states (or final states).
• In diagrams, the accepting states will be
denoted by double loops

05/02/2025 24
 DFA

Representation of 
o Transition Diagram
o Transition Table
o Transition Function

05/02/2025 25
 DFA

Transition Diagram
0 0

1 0

q0 q1 q2
1 1

M={ {q0, q1, q2}, {0,1}, , q0, q2}

05/02/2025 26
 DFA

Transition Table

Present Next State

State 0 1

 q0 q0 q0
q1 q0 q1
*q2 q0 q0

05/02/2025 27
 DFA

Transition Function

(q0, 0)= q0
(q0, 1)= q1
(q1, 0)= q2
(q1, 1)= q0
(q2, 0)= q1
(q2, 1)= q2

05/02/2025 28
 Example

0 1 0,1

q0 1 q1 0 q2

alphabet S = {0, 1} transition function d:

start state Q = {q0, q1, q2} inputs
initial state q0 0 1
accepting states F = {q0, q1} q0 q0 q1

states
q1 q2 q1
q2 q2 q2

05/02/2025 29
 Language of a DFA

The language of a DFA M=(Q, S, d, q0, F)

is the set of all strings over S accepted
by M i.e. L(M) and is denoted
L(M) = {w | w ∈ S* , d(q0 , w) = qf where qf ∈
F}
f

M: off on

• Language of M is {f, fff, fffff, …} = {f n: n

is odd}
05/02/2025 30
 Example

0 0
1 The set of all string over
q0 q1
1 {0,1} containing even no.
of 1’s
0 1
The set of all string over
1 {0,1} ending with 1’s
q0 q1
0

0 1 0,1
The set of all string over
q0 1 q1 0 q2 {0,1} does not contain 10
as substring

05/02/2025 31
 Exercise on DFA

1) Construct the DFA for the set of all string over {a,b}.
2) Construct the DFA for the set of all string over {a,b}
contain exactly 3a’s .
3) Construct the DFA that accepts all string over{a,b}
contains at most 3 a’s
4) Construct the DFA for the even number of a’s over {a,b}.
5) Construct the DFA for the set of all string contain three
consecutive a’s over {a,b}.
6) Construct the DFA that accepts all string over{a,b}
containing aba as substring.

05/02/2025 32
 Variation of Finite Automata

• Deterministic Finite Automat

– δ: Q × Σ → Q
• Non-Deterministic Finite Automata
– δ: Q x Σ → 2Q
• Non-Deterministic Finite Automata with Epsilon
• δ: Q x {Σ ∪ {ε}} → 2Q
• Finite Automata with output
(Q, Σ, Δ, δ, λ, q0) where Q , Σ, δ, and q0 are similar to DFA and Δ is
the set of output symbol and λ is out put function
• Moore Machine : the output is depend on present state λ : Q → Δ
• Mealy Machine : the output is depend on present state and current
input applied on the state λ : Q x Σ → Δ

05/02/2025 33
 NFA

In NFA, the machine can move from a present state to a

combination of states for an input symbol that is why it is
called non-deterministic. As the number of states are
finite, it is called Non-deterministic Finite Automata.

a q1

q0
a
q2

05/02/2025 34
 Formal definition of an NFA

• An NFA is represented as a 5 tuples,

M={Q, ∑, , q0, F}
Q= Non empty finite set of states
∑= Input alphabet
= Transition Function, : Q x ∑  2Q
q0= Initial State
F= Set of final states (F Q)

05/02/2025 35
 Difference between DFA and NFA
The transition from a state is to a single The transition from a state can be to a
particular next state for each input combination of states for each input
symbol. Hence it is called deterministic. symbol. Hence it is called non-
Means moves are unique. δ: Q × Σ → Q deterministic. It has several possible
moves. δ: Q x Σ → 2Q

Ɛ-transition is not allowed in DFA. NFA permits Ɛ-transition.

DFA takes more space. NFA takes less space.
DFA is as powerful as NFA. NFA is as powerful as DFA.
A string is accepted by a DFA, if it transits A string is accepted by a NDFA, if at least
to a final state. one of all possible transitions ends in a
final state.
Every DFA is an NFA. Every NFA is not a DFA.
The time needed to execute an i/p string is It takes more time to execute a string than
less than that is required by NFa DFA

36
 Examples of DFA

• Construct a DFA that accepts all strings over ∑={0,1} ending

with 1.
• Construct a DFA for L={w=(0,1)*| |w|=3n , n=0,1,2,...}
• Construct a DFA for L= { all binary strings containing substring
001 }

05/02/2025 37
 Examples of DFA

• Construct a DFA that accepts all strings over ∑={0,1} ending

with 1.

1
0 1

q0 q1
0

05/02/2025 38
 Examples of DFA

• Construct a DFA for L={w=(0,1)*| |w|=3n , n=0,1,2,...}

0, 1 0, 1

q0 q1 q2

0, 1

05/02/2025 39
 Examples of DFA

• Construct a DFA for L= { all binary strings containing substring

001 }
0, 1
1 0

0 0 1
q0 q1 q2 q3

05/02/2025 40
 Examples of DFA

• Construct a DFA for L= { all binary strings not containing

substring 001 }
0, 1
1 0

0 0 1
q0 q1 q2 q3

05/02/2025 41
 Examples of NFA

• Construct a NFA for L= { all strings beginning with aab }

a, b

a a b
q0 q1 q2 q3

05/02/2025 42
 Examples of NFA

• Construct a NFA over ∑={a,b,c,d} that recognises abd, aacd or

abdd.
b d
q1 q2 q3
a

a a c d
q0 q4 q5 q6 q7

a
b d d
q8 q9 q10 q11

05/02/2025 43
 Conversion of NFA to DFA

• Convert following NFA to DFA

1 0,1
0
0 1

q0 q0 q1
q0 q1
q1 q1 {q0,q1}
1

0 0 0,1
0 1

q0 q0 q1
1 1
q0 q1 [q0,q1]
q1 q1 [q0,q1]

[q0,q1] [q0,q1] [q0,q1]

05/02/2025 44
 Equivalence of NFA and DFA

Theorem: Every NFA has an equivalent DFA.

If a language L is accepted by an NFA then there exists an

equivalent DFA that accepts L.

05/02/2025 45
 Equivalence of NFA and DFA (Proof)

Let L is accepted by NFA N = (QN, ΣN, δN, q0N, FN).

Construct a DFA D= (QD, ΣD, δD, q0D, FD) as follows.
QN
QD is equal to the power set of QN, QD = 2
ΣD = ΣN =∑
q0D = {q0N}
FD is the set of states in QD that contain any element of FN.
δD is the transition function for D.
δD (q,a)= pq δN (q,a)for q ∈ QD and a ∈ Σ.
p is a single state from QN .
δD(q,a) is the union of all δN(p,a).
Now we will prove that for every x, L(D) = L(N)

05/02/2025 46
 Equivalence of NFA and DFA (Proof)
Basis Step
Let x be the empty string ε.
δD(q0D, x) = δD(q0D, ε)
= q0D
= {q0N }
= δN(q0N, ε)
= δN(q0N, x)

05/02/2025 47
 Equivalence of NFA and DFA (Proof)
Inductive Step
Assume that for any y with |y| ≥ 0, δD(q0D, y) = δN(q0N, y).
If we let n = |y|, then we need to prove that for a string z with |z| = n + 1, δD(q0D, z) = δN(q0N, z) .
We can represent the string z as a concatenation of string y (|y| = n) and symbol a from the
alphabet Σ (a ∈ Σ). So, z = ya.
δD(q0D, z) = δD(q0D, ya)
= δD(δN(q0D, y) ,a)
= δD(δN(q0N, y) ,a) By assumption
=  p δN(q0N, y) δN(q0N, y) By definition of δD
= δN(q0N, ya)
= δN(q0N, z)
DFA D accepts a string x iff δD(q0D, x)  FD . From the above it follows that D accepts x iff δN(q0N, x) 
FN = .
So a string is accepted by DFA D if, and only if, it is accepted by NFA N.
05/02/2025 48
 NFA with Ɛ- Transition
0 1

ε
q0 q1

We extend the class of an NFA by allowing ε transitions:

• The automaton may be allowed to change its state without
reading the input symbol.
• Such transitions are depicted by labeling the appropriate arcs
with ε.
• ‘ε’ does not belong to any alphabet (∑).

05/02/2025 49
 Why Ɛ- NFA ?/

• ε -NFAs add a convenient feature.

• Through ε –NFAs we can implement some complex languages
easily.
• They do not extend the power of an NFA.
• Both NFAs and ε-NFAs have same power.

05/02/2025 50
 Formal definition of an Ɛ- NFA

• An NFA is represented as a 5 tuples,

M={Q, ∑, , q0, F}
Q= Non empty finite set of states
∑= Input alphabet
= Transition Function, : Q X (∑Ɛ)  2Q
q0= Initial State
F= Set of final states (F Q)

05/02/2025 51
 Example of ε -NFA

• Design an NFA for L={ apbqcr| p,q,r 0}.

a b c

ε ε
q0 q1 q2

05/02/2025 52
 Example of ε -NFA

• Design an NFA for L={ an| n is even or divisible by 3}.

a
ε q1 q2

q0 a

ε
q3 a q4 a q5

05/02/2025 53
 ε –Closure of a state

• The ε-closure of the state q, denoted as ε-Closure(q), is the

set that contains q, together with all states that can be
reached starting at q by following only ε-transitions.
a b c

ε ε
q0 q1 q2

• ε-Closure(q0) = {q0, q1, q2}

• ε-Closure(q1) = {q1, q2}
• ε-Closure(q2) = {q2}

05/02/2025 54
 Conversion of ε –NFA to NFA
a b c (q0, a)= ε-Closure(ε-Closure(q0), a)
= ε-Closure({ q0,q1,q2},a)
ε ε = ε-Closure(q0)
q0 q1 q2 = {q0, q1, q2}

States ε-Closure a b c

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

q1 {q1, q2} q1  {q1, q2} {q2}

q2 {q2} q2   {q2}

a b c

a, b b, c
q0 q1 q2

a, b, c
05/02/2025 55
 Minimization of DFA

• Minimization of a DFA refers to the removal of those states of a DFA,

whose presence or absence in a DFA does not affect the language
accepted by the automata.

• The states that can be eliminated from automata are:

 Unreachable or inaccessible states.
 Dead states.
 Non-distinguishable or indistinguishable state or equivalent
states.

05/02/2025 56
 Minimization of DFA

• Minimize the following DFA:

0
0 Transition Table

0 1
B 1 D
0 A B C

B B D
A 0 1
0 C B C

1 D B E
C E *E B C
1

05/02/2025 57
 Minimization of DFA
• Eqivalent State
Two states qi and qj are equivalent or indistinguishable (for the future), if,
when started in these states, every string causes the machine to either end up
in an accepting state for both or end up in a non-accepting state for both.
qi qm
a

qj qn
a

If qm and qn are distinguishable, then so are qi and qj

05/02/2025 58
 Minimization of DFA
Suppose there is a DFA D < Q, Σ, q0, δ, F > which recognizes a language L. Then
the minimized DFA D < Q’, Σ, q0, δ’, F’ > can be constructed for language L as:
 Step 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
 0.
 Step 2: Initialize k = 1
 Step 3: Find k by partitioning the different sets of k-1. In each set of k-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 k.
 Step 4: Stop when k = k-1 (No change in partition)
 Step 5: All states of one set are merged into one. No. of states in minimized
DFA will be equal to no. of sets in k.

05/02/2025 59
 Minimization of DFA

Find Equivalence classes

Transition Table
0 1
0= {A,B,C,D} {E}
A B C 1= {A,B,C} {D} {E}
B B D 2= {A,C} {B} {D} {E}
C B C
3= {A,C} {B} {D} {E}
D B E
2= 3 ,so stop here.
*E B C

05/02/2025 60
 Minimization of DFA

Transition Table
{A,C} {B} {D} {E}

0 1 0
0
A B C

B B D B 1 D
0
C B C

D B E AC 0 1
0
*E B C
1
E

05/02/2025 61
 Minimization of DFA

Using Table Filling Method (Myhill-Nerode Theorem)

Step 1: Draw a table for all pairs of states (P,Q) not necessarily
connected directly [All are unmarked initially].

Step 2: Consider every state pair (P,Q) in the DFA where P ∈ F and
Q ∉ F or vice versa and mark (X) them. [Here F is the set of final
states].

05/02/2025 62
 Minimization of DFA

Using Table Filling Method (Myhill-Nerode Theorem)

Contd…

Step 3: Repeat this step until we cannot mark anymore states − If

there is an unmarked pair (P, Q ), such that {δ(P , a), δ (Q , a)} is
marked then mark (P,Q), where a ∈ ∑.

Step 4: Combine all the unmarked pair (P , Q ) and make them a

single state in the reduced DFA.

05/02/2025 63
 Minimization of DFA

Minimize the following DFA.

0, 1

1 1
B D F
1
0 0
1
0

A C 0 E
1
0

05/02/2025 64
 Minimization of DFA

Step 1: Draw a Table for all pair of states (P,Q).

A B C D E F
A
B
C
D
E
F

05/02/2025 65
 Minimization of DFA

Step 2: Mark every state pair (P,Q) in the DFA where P ∈ F and Q ∉ F .

A B C D E F
A
B
C X X
D X X
E X X
F X X X

05/02/2025 66
 Minimization of DFA

Step 3: − If there is an unmarked pair (P, Q ), such that {δ(P , a), δ (Q , a)} is
marked then mark (P,Q).

A B C D E F
A
B
C X X
D X X
E X X
F X X X X X

05/02/2025 67
 Minimization of DFA

•After step 3, we have got state combinations {a, b} {c, d} {c, e} {d, e} that
are unmarked.
•We can recombine {c, d} {c, e} {d, e} into {c, d, e}.
•Hence we got two combined states as − {a, b} and {c, d, e}.
•So the final minimized DFA will contain three states {f}, {a, b} and {c, d,
e}.
0 0 0, 1

1 1
[AB] [CDE] F

05/02/2025 68
 Daily Quiz

1. One language can be expressed by more than one FA”. This

statement is ______
a) True
b) False
c) Some times true & sometimes false
d) None of these

2. Can a DFA simulate NFA?

e) NO
f) YES
g) SOMETIMES
h) Depends on NFA

05/02/2025 69
 Daily Quiz
3. Which of the following statements is wrong ?

A. The language accepted by finite automata are the languages

denoted by regular expressions
B. For every DFA there is a regular expression denoting its language
C. For a regular expression r, there does not exist NFA with L(r) any
transit that accept
D. None of these

4. An automation is a __________ device and a grammar is a

__________ device.
A. generative, cognitive
B. generative, acceptor
C. acceptor, cognitive
D. cognitive, generative
05/02/2025 70
 Daily Quiz

5. Finite state machines _________ recognize palindromes

A. can
B. can't
C. may
D. may not

6. FSM shown in the figure

A. all strings
B. no string
C. ε- alone
D. none of these

05/02/2025 71
 Daily Quiz

7. A FSM can be used to add how many given integers?

a) 1
b) 2
c) 3
d) Any number of integers

8. The basic limitation of a FSM is that

e) It cannot remember arbitrary large amount of information
f) It sometimes recognizes grammar that are not regular
g) It sometimes fails to recognize grammars that are regular
h) All of the above

05/02/2025 72
 Daily Quiz

9. Finite automata are used for pattern matching in text

editors for
a) Compiler lexical analysis
b) Programming in localized application
c) Both A and B
d) None of the above

10. The language accepted by finite automata is

e) Context free
f) Regular
g) Non regular
h) None of these

05/02/2025 73
 Finite Automata with Output

Objective of the Topic

The objective of the topic is to make the student able to:

• Understand the requirement of FA with output.
• Implement Mealy and Moore machine.
• Convert Mealy machine to Moore machine and vice-versa.

05/02/2025 74
 Finite Automata with Output

• The Finite Automata Discussed so far have limited capability i.e.

accepting or rejecting a string.
• Finite Automata with output do not have final state.
•Finite Automata with output are of two types:
• Mealy Machine
• Moore Machine

05/02/2025 75
 Finite Automata with Output

• Mealy Machine
• The out put is associated with transition. The output depends on present
state and present input.
: Q X ∑  

• Moore Machine
• The output is associated with present state. The output depends on
present state only.
: Q  

05/02/2025 76
 Formal Definition of Mealy Machine

• Mealy machine is described by 6-tuples - (Q, Σ, Δ, δ, λ, q0)

where
Q = Finite non-empty set of states;
Σ = Set of input alphabets.
Δ = Set of output alphabets.
δ = Transitional function mapping Q X Σ → Q
λ = Output function mapping Q X Σ → Δ
q0 = Initial state

05/02/2025 77
 Example of Mealy Machine

Design a Mealy machine that accepts all strings over ∑={a, b}

ending in aa or bb.
a/1
Present Next State
q2 State
a /0 a b

b/0
a/0

q0
q0 q2, 0 q1, 0
b/0
q1 q2, 0 q1, 1
q1
q2 q2, 1 q1,0
b/1

05/02/2025 78
 Formal Definition of Moore Machine

• Moore machine is described by 6-tuples - (Q, Σ, Δ, δ, λ, q0)

where
Q = Finite non-empty set of states;
Σ = Set of input alphabets.
Δ = Set of output alphabets.
δ = Transitional function mapping Q X Σ → Q
λ = Output function mapping Q → Δ
q0 = Initial state

05/02/2025 79
 Example of Moore Machine

Create a Moore machine that counts number of a mod3. ∑={a, b}.

b b b

a a
q0/0 q1/1 q2/2

Present Next State Output

a State
a b

q0 q2 q1 0

q1 q2 q1 1

q2 q2 q1 2
05/02/2025 80
Conversion from Mealy machine to Moore machine

Step 1: For each state q determine the number of outputs that are
associated with q in Next state column of transition table of the Mealy
machine.
Step 2: If the outputs corresponding to state q in the next state
columns are same, then retain state q as it is.
Else, break q into different states with the number of new states being
equal to the number of different outputs of q.
Step 3: Rearrange the states and outputs in the format of Moore
machine.

05/02/2025 81
Conversion from Mealy machine to Moore machine

Step 4: If the output in the constructed state table corresponding to

the initial state is 1, then this specifies the acceptance of the null string
Ɛ by Mealy machine. Hence, to make both the Mealy and Moore
machines equivalent, we either need to ignore the corresponding to
null string or we need to insert a new initial state at beginning whose
output is 0; the other row elements in this case would remain the
same.

05/02/2025 82
Conversion from Mealy machine to Moore machine
Convert given Mealy machine to Moore machine.

Mealy Machine Moore Machine

Present Next State Present Next State Output
State State
a b a b

q0 q3, 0 q1, 1

q0 q3 q11 1
q1 q0, 1 q3, 0
q10 q0 q3 0
q2 q2, 1 q2, 0
q11 q0 q3 1
q3 q1, 0 q0, 1
q20 q21 q20 0
Split q1 into q10 and q11 q21 q21 q20 1
and
Split q2 into q20 and q21 q3 q10 q0 0

05/02/2025 83
Conversion from Moore machine to Mealy machine

For understanding the conversion of Moore machine to Mealy machine, let

us take an example:
Suppose the Moore machine transition table is:
Present Next State Output
State
a b

p s q 0

q q r 1

r r s 0

s s p 0

05/02/2025 84
Conversion from Moore machine to Mealy machine

First of all take the Mealy machine transition table format, and copy all
the Moore machine transition table states into Mealy machine transition
table.
Present Next State
State
a b

p s q

q q r

r r s

s s p

05/02/2025 85
 Conversion from Moore m/c to Mealy m/c

Now in the Moore machine, the output of state p is 0. So make the output of p
in the Mealy machine next state column of the above table is 0. Same process
is repeated for q, r and s.
Moore Machine Mealy Machine
Present Next State
Present Next Output State
State State a b
a b

p s, 0 q, 1
p s q 0 q q, 1 r, 0
q q r 1 r r, 0 s, 0
r r s 0 s s, 0 p, 0
s s p 0
05/02/2025 86
Difference Between Mealy And Moore Machine

BASIS OF COMPARISON MEALY MACHINE MOORE MACHINE

Mealy machine changes its Output of Moore machine only
Description output based on its current depends on its current state
input and present state. and not on the current input.
Output Output is placed on transition. Output is placed on transition.

Output Function : Q X ∑   : Q  
Counter A counter is not a Mealy A counter is a Moore machine.
machine.
Design Not necessarily easy to design. Easy to design.
It produce n length output It produce n+1 length output
Length of Out put String string corresponding to n length string corresponding to n length
input String input String

05/02/2025 87
 Daily Quiz
1. Given: ∑= {a, b}L= {xϵ∑*|x is a string combination}∑4 represents which
among the following? *
A. {aa, ab, ba, bb}
B. {aaaa, abab, ε, abaa, aabb}
C. {aaa, aab, aba, bbb}
D. All of the mentioned

2. Converting each of the final states of F to non-final states and old non-final
states of F to final states, FA thus obtained will reject every string belonging
to L and will accept every string, defined over Σ, not belonging to L. is called
E. Transition Graph of L
F. Regular expression of L
G. Complement of L
H. Finite Automata of L

05/02/2025 88
 Daily Quiz

3. Myhill Nerode theorem is consisting of the followings,

A. L partitions Σ into distinct classes.
B. If L is regular then, L generates finite number of classes.
C. If L generates finite number of classes, then L is regular.
D. All of above

4. The part of an FA, where the input string is placed before it is run, is
called ______
E. State
F. Transition
G. Input Tape
D. Output Tape

05/02/2025 89
 Daily Quiz

5. Which of the following is an application of Finite Automaton?

A. Compiler Design
B. Grammar Parsers
C. Text Search
D. All of the mentioned

6. Which of the following is a not a part of 5-tuple finite automata?

E. Input alphabet
F. Transition function
G. Initial State
H. Output Alphabet

05/02/2025 90
 Daily Quiz

7. John is asked to make an automaton which accepts a given string for all the
occurrence of ‘1001’ in it. How many number of transitions would John use such
that, the string processing application works?
A. 9
B. 11
C. 12
D. 15

8. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
E. 10
F. 11
G. 12
H. 13

05/02/2025 91
 Daily Quiz

9. A binary string is divisible by 4 if and only if it ends with:

a) 100
b) 1000
c) 1100
d) 0011

10. Let N (Q, ∑, δ, q0, A) be the NFA recognizing a language L. Then for
a DFA (Q’, ∑, δ’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}
c) Q’={q0}
d) All of the mentioned

05/02/2025 92
 Weekly Assignment
1. Design a deterministic finite automaton(DFA) for the following
language over the set of input alphabet {0,1}

[CO1]
• All strings of 0’s and 1’s such that no of 0’s are even and 1’s are odd.
• All strings of 0’s and 1’s with at least two consecutive 0’s.
• All strings of 0’s and 1’s beginning with 1 and not having two
consecutive zeroes.
• All strings of 0’s and 1’ s not containing 101 as substring.
• All strings of 0’s and 1’s whose last two symbols are same.

05/02/2025 93
 Weekly Assignment
3. Prove that NFA is equivalent to DFA. [CO1]
4. Construct NFA accepting the set of all strings over {a, b} ending in
aba. Use it to construct a DFA accepting the same set of strings.
[CO1]
5. Design a NFA with epsilonthat accepts {a, b}*baaa.[CO1]
6. Design a NFA that accepts (a+b)*(ab+bba) (a+b)* i.e. strings
containing either ab or bba as substring . convert it into DFA.
[CO1]
7. Differentiate between DFA and NDFA with suitable example?
[CO1]
8. Describe various Application and Limitations of Finite Automata.
[CO1]

05/02/2025 94
 Weekly Assignment
2. Design a Non-deterministic finite automaton(NFA) for the following
language over the set of input alphabet {0,1}
[CO1]
• All strings of 0’s and 1’s such that 3rd symbol from right end is 1.
• All strings of 0’s and 1’s such that either the 2nd or 3rd position from
the right end has a 1.
• All strings of 0’s and 1’s satisfying 1m01n : m, n>=1.
• All strings of 0’s, 1’s and 2’s with any no of 0’s followed by any no of
1’s and any no of 1’s followed by any no of 2’s.
• All strings of 0’s and 1’s ending in1 and not containing substring 00.

05/02/2025 95
 MCQ s

1. A binary string is divisible by 4 if and only if it ends with:

A. 100
B. 1000
C. 1100
D. 0011

2. Recognizing capabilities of NFSM and DFSM

E. May be different
F. May be same
G. Must be different
H. None of the above

05/02/2025 96
 MCQ s

3. Which minimum state FA is equivalent to following FA

ANS : (A)

05/02/2025 97
 MCQ s

4. The minimum number of states required to recognize an octal

number divisible by 3 are/is
A. 1
B. 3
C. 5
D. 7

5. Which of the following is/ are regular

E. a string of a' s in perfect square
F. a string of palindrom over {a,b}
G. a string of odd no of a's over {a,b}
H. a string of equal no of a's and b's over {a,b}

05/02/2025 98
 MCQ s

6. If two finite state machines are equivalent, they should have the
same number of
A. states
B. edges
C. states and edges
D. none of these

7. The word 'formal' in formal languages means

A. the symbols used have well-defined meaning
B. they are unnecessary, in reality
C. only form of the string of symbols is significant
D. Both (a) and (b)

05/02/2025 99
 MCQ s

8. The main difference between a DFSA and an NDFSA is

A. in DFSA, ε transition may be present
B. in NDFSA, ε transitions may be present
C. in DFSA, from any given state, there can't be any alphabet leading to two
diferent states
D. in NDFSA, from any given state, there can't be any alphabet leading to two
different states

9. Palindromes can't be recognized by any FSM because

A. FSM can't remember arbitrarily large of information
B. FSM can't deterministically fix the mid-point
C. even if mid-point is known, FSM be can't be found whether, second half of
the string matches the first half
D. all of these

05/02/2025 100
 Expected Questions for University Exam
• Design a NFA that accepts all the strings for input alphabet {a,b}
containing the substring abba.
• Convert NFA into equivalent DFA by taking any suitable example.
• Design the DFA that accepts an even number of a’s and even number
of b’s.
• Construct the minimum state automata equivalent to DFA described
below:

• Check with the comparison method for testing equivalence of two FA

given below:

05/02/2025 101
 Summary

• Finite automata is a machine that acccepts regular languages.

• FA has its application in many fields like compiler design, digital
circuits, etc.
• NFA and DFA has same expressive power.
• NFA is easy to construct than DFA.
• Every NFA is equivalent to DFA.
• Myhill-Nerode theorem is used to optimize the FA.

05/02/2025 102
References

• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2001). Introduction

to automata theory, languages, and computation. Acm Sigact
News, 32(1), 60-65.
• Linz, P. (2006). An introduction to formal languages and
automata. Jones & Bartlett Learning.
• Mishra, K. L. P., & Chandrasekaran, N. (2006). Theory of
Computer Science: Automata, Languages and Computation. PHI
Learning Pvt. Ltd..

05/02/2025 103
 Thank You

05/02/2025 104