Regular Expressions

Module 2

Dr. Vibha Nehra

Department of Computer Science & Engineering

Amity School of Engineering and Technology

Amity University Uttar Pradesh, Noida

December 8, 2025
 Learning Objectives and Outcomes

Sub-topic Learning Objective Learning Outcomes

Regular Expression To understand the concept of To become familar with regular
regular expression expression
Two way Finite To understand the relevance To understand the logic behind
Automata of 2 way finite automata and importance of 2 way finite
automata
Finite Automata To understand the machine To get familiar with Mealy and
with output with output Moore machine.
Properties of To understand the properties To understand properties of
regular sets of regular set regular set
Pumping lemma To understand the idea and To understand the idea behind
for regular sets relevance of pumping lemma pumping lemma for regular sets
My-Hill-Nerode To understand My-Hill-Nerode To understand relevance of the
Theorem Theorem theroem

Department of Computer Science and Engineering RE December 8, 2025 2/68

 Outline

1 Regular Expression

2 Two way finite automata

3 Pumping Lemma for Regular Sets

4 My-Hill-Nerode Theorem

5 Finite Automata with Output

Department of Computer Science and Engineering RE December 8, 2025 3/68

 Regular Expression

Regular Expression

A language is regular if there exists a finite acceptor for it

∴ Every regular language can be described as DFA or NDFA

Department of Computer Science and Engineering RE December 8, 2025 4/68

 Regular Expression

Regular Expression

A language is regular if there exists a finite acceptor for it

∴ Every regular language can be described as DFA or NDFA
Regular Expression: Algebraic decription of languages

Department of Computer Science and Engineering RE December 8, 2025 4/68

 Regular Expression

Regular Expression

A language is regular if there exists a finite acceptor for it

∴ Every regular language can be described as DFA or NDFA
Regular Expression: Algebraic decription of languages
Let Σ be a given alphabet, then:
1 ϕ, λ and a ∈ Σ are all regular expressions, called Primitive regular
expressions.
2 If r1 and r2 are regular expressions, so are r1 + r2 ,r1 .r2 ,r1 ∗ and (r1 )
3 A string is a regular expression if and only if it can be derived from
primitive regular expressions by a finite number of applications of
the rules in (2)

Department of Computer Science and Engineering RE December 8, 2025 4/68

 Regular Expression

Regular Expression

A language is regular if there exists a finite acceptor for it

∴ Every regular language can be described as DFA or NDFA
Regular Expression: Algebraic decription of languages
Let Σ be a given alphabet, then:
1 ϕ, λ and a ∈ Σ are all regular expressions, called Primitive regular
expressions.
2 If r1 and r2 are regular expressions, so are r1 + r2 ,r1 .r2 ,r1 ∗ and (r1 )
3 A string is a regular expression if and only if it can be derived from
primitive regular expressions by a finite number of applications of
the rules in (2)
Example: For Σ={a,b,c}, the string (a + b.c)∗ .(c + ϕ) is a
regular expression
while (a+b+) is not a regular expression.

Department of Computer Science and Engineering RE December 8, 2025 4/68

 Regular Expression

Language Associated with Regular Expression

The language l(r) denoted by any regular expression ’r’ is defined
by following rules
1 ϕ is a R.E. denoting empty set
2 λ is a R.E. denoting {λ}
3 For every a ∈ Σ, a is a R.E. denoting {a}
If r1 and r2 are R.E. , then
4 L(r1 +r2 )=L(r1 )∨L(r2 )
5 L(r1 .r2 )=L(r1 )L(r2 )
6 L((r1 ))=L(r1 )
7 L(r1∗ )=(L(r1 ))∗

Department of Computer Science and Engineering RE December 8, 2025 5/68

 Regular Expression

Language Associated with Regular Expression

The language l(r) denoted by any regular expression ’r’ is defined
by following rules
1 ϕ is a R.E. denoting empty set
2 λ is a R.E. denoting {λ}
3 For every a ∈ Σ, a is a R.E. denoting {a}
If r1 and r2 are R.E. , then
4 L(r1 +r2 )=L(r1 )∨L(r2 )
5 L(r1 .r2 )=L(r1 )L(r2 )
6 L((r1 ))=L(r1 )
7 L(r1∗ )=(L(r1 ))∗
Example: For Σ={a,b}, the expression
r=(a + b)∗ (a+bb) is regular

Department of Computer Science and Engineering RE December 8, 2025 5/68

 Regular Expression

Language Associated with Regular Expression

The language l(r) denoted by any regular expression ’r’ is defined
by following rules
1 ϕ is a R.E. denoting empty set
2 λ is a R.E. denoting {λ}
3 For every a ∈ Σ, a is a R.E. denoting {a}
If r1 and r2 are R.E. , then
4 L(r1 +r2 )=L(r1 )∨L(r2 )
5 L(r1 .r2 )=L(r1 )L(r2 )
6 L((r1 ))=L(r1 )
7 L(r1∗ )=(L(r1 ))∗
Example: For Σ={a,b}, the expression
r=(a + b)∗ (a+bb) is regular
=⇒ L(r)={a,bb,aa,abb,ba,bbb,....}

Department of Computer Science and Engineering RE December 8, 2025 5/68

 Regular Expression

Language Associated with Regular Expression

The language l(r) denoted by any regular expression ’r’ is defined
by following rules
1 ϕ is a R.E. denoting empty set
2 λ is a R.E. denoting {λ}
3 For every a ∈ Σ, a is a R.E. denoting {a}
If r1 and r2 are R.E. , then
4 L(r1 +r2 )=L(r1 )∨L(r2 )
5 L(r1 .r2 )=L(r1 )L(r2 )
6 L((r1 ))=L(r1 )
7 L(r1∗ )=(L(r1 ))∗
Example: For Σ={a,b}, the expression
r=(a + b)∗ (a+bb) is regular
=⇒ L(r)={a,bb,aa,abb,ba,bbb,....}
=⇒ L(r) is the set of all strings on {a,b}, terminated by either ’a’
or ’bb’.
Department of Computer Science and Engineering RE December 8, 2025 5/68
 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}
For Σ ={0,1}. Give a regular expression ’r’ such that
L(r)={w∈ Σ∗ |w has atleast one pair of consequtive zeroes}

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}
For Σ ={0,1}. Give a regular expression ’r’ such that
L(r)={w∈ Σ∗ |w has atleast one pair of consequtive zeroes}
Solution: r=(0 + 1)∗ 00(0 + 1)∗

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}
For Σ ={0,1}. Give a regular expression ’r’ such that
L(r)={w∈ Σ∗ |w has atleast one pair of consequtive zeroes}
Solution: r=(0 + 1)∗ 00(0 + 1)∗
Find R.E. for language
L={w ∈ {0, 1}∗ |w has no pair of consecutive zeroes}

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}
For Σ ={0,1}. Give a regular expression ’r’ such that
L(r)={w∈ Σ∗ |w has atleast one pair of consequtive zeroes}
Solution: r=(0 + 1)∗ 00(0 + 1)∗
Find R.E. for language
L={w ∈ {0, 1}∗ |w has no pair of consecutive zeroes}
Solution: r=(1 + 01)∗ (0 + λ)
r=(1∗ 011∗ )∗ (0 + λ) + 1∗ (0 + λ)

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}
For Σ ={0,1}. Give a regular expression ’r’ such that
L(r)={w∈ Σ∗ |w has atleast one pair of consequtive zeroes}
Solution: r=(0 + 1)∗ 00(0 + 1)∗
Find R.E. for language
L={w ∈ {0, 1}∗ |w has no pair of consecutive zeroes}
Solution: r=(1 + 01)∗ (0 + λ)
r=(1∗ 011∗ )∗ (0 + λ) + 1∗ (0 + λ)
Find all strings in L((a + b)∗ b(a + ab)∗ ) of length less than 4

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Language Associated with Regular Expression

r=(aa)∗ (bb)∗ b
denotes the set of all strings with even number of a’s followed
by an odd number of b’s
L(r)={a2n b 2m+1 |n≥0, m≥0}
For Σ ={0,1}. Give a regular expression ’r’ such that
L(r)={w∈ Σ∗ |w has atleast one pair of consequtive zeroes}
Solution: r=(0 + 1)∗ 00(0 + 1)∗
Find R.E. for language
L={w ∈ {0, 1}∗ |w has no pair of consecutive zeroes}
Solution: r=(1 + 01)∗ (0 + λ)
r=(1∗ 011∗ )∗ (0 + λ) + 1∗ (0 + λ)
Find all strings in L((a + b)∗ b(a + ab)∗ ) of length less than 4
Find R.E. for set {an b m :(n+m) is even}

Department of Computer Science and Engineering RE December 8, 2025 6/68

 Regular Expression

Automata and Regular Expression

Automaton for L(r1 + r2 )

Department of Computer Science and Engineering RE December 8, 2025 7/68

 Regular Expression

Automata and Regular Expression

Automaton for L(r1 + r2 )

Automaton for L(r1 .r2 )

Department of Computer Science and Engineering RE December 8, 2025 7/68

 Regular Expression

Automata and Regular Expression

Automaton for L(r1 + r2 )

Automaton for L(r1 .r2 )

Automaton for L(r1 ∗ )

Department of Computer Science and Engineering RE December 8, 2025 7/68

 Regular Expression

Automata and Regular Expression

Generalized Transition Graph: A transition graph whose edges
are labelled as R.E.

Department of Computer Science and Engineering RE December 8, 2025 8/68

 Regular Expression

Automata and Regular Expression

Generalized Transition Graph: A transition graph whose edges
are labelled as R.E.
Example: L(r)=(a∗ + a∗ (a + b)c ∗ )

Department of Computer Science and Engineering RE December 8, 2025 8/68

 Regular Expression

Automata and Regular Expression

Generalized Transition Graph: A transition graph whose edges
are labelled as R.E.
Example: L(r)=(a∗ + a∗ (a + b)c ∗ )
Equivalence of Generalized Transition Graph:
Let L be a regular expression. Then, there exists some NFA
that accepts L(r). Consequently, L(r) is a regular language.
Find NDFA which accepts L(r) where r=(a + bb)∗ (ba∗ + λ)

Department of Computer Science and Engineering RE December 8, 2025 8/68

 Regular Expression

Automata and Regular Expression

The Strings denoted by such regular expressions are a subset

of the language accepted by GTG, with full language being
the union of all such generated subsets

Department of Computer Science and Engineering RE December 8, 2025 9/68

 Regular Expression

Automata and Regular Expression

The Strings denoted by such regular expressions are a subset

of the language accepted by GTG, with full language being
the union of all such generated subsets
Example: The language accepted by the following GTG is

L(a∗ + a∗ (a + b)c∗)
State Elimination method
Arden’s Theorem

Department of Computer Science and Engineering RE December 8, 2025 9/68

 Regular Expression

Automata and Regular Expression

State Elimination method

1 Initial State should not have any incoming edge
2 Final State should not have any outgoing edge
3 Only 1 final state
4 Eliminate each non-initial/final vertex one by one

Department of Computer Science and Engineering RE December 8, 2025 10/68

 Regular Expression

State Elimination Method

1. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 11/68

 Regular Expression

State Elimination Method

1. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 11/68

 Regular Expression

State Elimination Method

1. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 11/68

 Regular Expression

State Elimination Method

1. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 11/68

 Regular Expression

State Elimination Method

1. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 11/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

2. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 12/68

 Regular Expression

State Elimination Method

3. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 13/68

 Regular Expression

State Elimination Method

3. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 13/68

 Regular Expression

State Elimination Method

3. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 13/68

 Regular Expression

State Elimination Method

3. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 13/68

 Regular Expression

State Elimination Method

3. Find R.E. for given DFA

Department of Computer Science and Engineering RE December 8, 2025 13/68

 Regular Expression

State Elimination Method

1 Find R.E. for the given DFA

Department of Computer Science and Engineering RE December 8, 2025 14/68

 Regular Expression

State Elimination Method

1 Find R.E. for the given DFA

2 Find R.E. for the given DFA

Department of Computer Science and Engineering RE December 8, 2025 14/68

 Regular Expression

Identities for Regular Expression

1 ϕ+R=R
2 ϕR = R ϕ = ϕ
3 ΛR = RΛ =R
4 Λ∗ = Λ and ϕ∗ = Λ
5 R+R=R
6 R ∗R ∗ = R ∗
7 RR ∗ = R ∗ R
8 (R ∗ )∗ = R ∗
9 Λ + RR ∗ = R ∗ = Λ + R ∗ R
10 (PQ)∗ P = P(QP)∗
11 (P + Q)∗ = (P ∗ Q ∗ )∗ =(P ∗ + Q ∗ )∗
12 (P+Q)R = PR + QR and R(P+Q) = RP + RQ

Department of Computer Science and Engineering RE December 8, 2025 15/68

 Regular Expression

ϵ-NFA
=⇒ Moving without reading a symbol from Input Tape.

Department of Computer Science and Engineering RE December 8, 2025 16/68

 Regular Expression

ϵ-NFA
=⇒ Moving without reading a symbol from Input Tape.

State/Input 0 1 ϵ
A B,C A B
B - B C
C C C -

Department of Computer Science and Engineering RE December 8, 2025 16/68

 Regular Expression

ϵ-NFA
=⇒ Moving without reading a symbol from Input Tape.

State/Input 0 1 ϵ
A B,C A B
B - B C
C C C -

Epsilon Closure
ϵ-closure for a given state X is a set of States which can be
reached from states X with only (null) or ϵ moves including the
state X itself.

Department of Computer Science and Engineering RE December 8, 2025 16/68

 Regular Expression

ϵ-NFA
=⇒ Moving without reading a symbol from Input Tape.

State/Input 0 1 ϵ
A B,C A B
B - B C
C C C -

Epsilon Closure
ϵ-closure for a given state X is a set of States which can be
reached from states X with only (null) or ϵ moves including the
state X itself.
Example: ϵ closure (A)={A,B,C}
ϵ closure (B)={B,C}
ϵ closure (C)={C}
Department of Computer Science and Engineering RE December 8, 2025 16/68
 Regular Expression

Conversion of NFA with ϵ to DFA

Steps:
1 Take ϵ closure of initial state as begining state
2 Find states that can be traversed from present from present
state for each input symbol
3 If any new state is found, repeat step 2 till we get no new
state in the transition table.
4 Mark states containing final states as new final state.

State/Input 0 1
{A,B,C} {B,C} {A,B,C}

Department of Computer Science and Engineering RE December 8, 2025 17/68

 Regular Expression

Conversion of NFA with ϵ to DFA

Steps:
1 Take ϵ closure of initial state as begining state
2 Find states that can be traversed from present from present
state for each input symbol
3 If any new state is found, repeat step 2 till we get no new
state in the transition table.
4 Mark states containing final states as new final state.

State/Input 0 1
{A,B,C} {B,C} {A,B,C}
{B,C} {C} {B,C}

Department of Computer Science and Engineering RE December 8, 2025 17/68

 Regular Expression

Conversion of NFA with ϵ to DFA

Steps:
1 Take ϵ closure of initial state as begining state
2 Find states that can be traversed from present from present
state for each input symbol
3 If any new state is found, repeat step 2 till we get no new
state in the transition table.
4 Mark states containing final states as new final state.

State/Input 0 1
{A,B,C} {B,C} {A,B,C}
{B,C} {C} {B,C}
{C} {C} {C}

Department of Computer Science and Engineering RE December 8, 2025 17/68

 Regular Expression

Conversion of NFA with ϵ to DFA

Steps:
1 Take ϵ closure of initial state as begining state
2 Find states that can be traversed from present from present
state for each input symbol
3 If any new state is found, repeat step 2 till we get no new
state in the transition table.
4 Mark states containing final states as new final state.

State/Input 0 1
{A,B,C} {B,C} {A,B,C}
{B,C} {C} {B,C}
{C} {C} {C}

Now, create transition diagram

Department of Computer Science and Engineering RE December 8, 2025 17/68

 Regular Expression

Arden’s Theorem
Let P and Q be two regular expressions over Σ. If P doesnot
contain Λ, then the following equation in R i.e. R=Q+RP
has a unique solution R=QP ∗
Proof:
R = Q + RP (1)
putting ”R=Q+RP” in equation 1
R=Q+QP+RPP
putting R recursively again and again
we get:
R=Q+QP+QP 2 +QP 3 + . . .
R= Q (Λ + P + P 2 + P 3 + . . .)
R=QP ∗

Department of Computer Science and Engineering RE December 8, 2025 18/68

 Regular Expression

Arden’s Theorem
Let P and Q be two regular expressions over Σ. If P doesnot
contain Λ, then the following equation in R i.e. R=Q+RP
has a unique solution R=QP ∗
Proof:
R = Q + RP (1)
putting ”R=Q+RP” in equation 1
R=Q+QP+RPP
putting R recursively again and again
we get:
R=Q+QP+QP 2 +QP 3 + . . .
R= Q (Λ + P + P 2 + P 3 + . . .)
R=QP ∗
Assumptions:
The transition diagram must not have null transitions.
It must only 1 initial state

Department of Computer Science and Engineering RE December 8, 2025 18/68

 Regular Expression

Arden’s Theorem I
1. Find R.E. for the following DFA

q1 = q1 0 + q3 0 + ∧ (2)
q2 = q1 1 + q2 1 + q3 1 (3)
q3 = q2 0 (4)
putting equation 4 in equation 3

q2 = q1 1 + q2 1 + q3 1
= q1 1 + q2 1 + (q2 0)1
= q1 1 + q2 (1 + 01)
Department of Computer Science and Engineering RE December 8, 2025 19/68
 Regular Expression

Arden’s Theorem II
Applying Arden’s Theorem
q2 = q1 1(1 + 01)∗ (5)
putting 5 in equation 2
q1 = q1 0 + q3 0 + ∧
= q1 0 + q2 00 + ∧
= q1 0 + (q1 1(1 + 01)∗ 00) + ∧
q1 (0 + 1(1 + 01)∗ 00) + ∧
using arden’s theorem again

∗
q1 = ∧(0 + 1(1 + 01)∗ 00)
∗
(0 + 1(1 + 01)∗ 00)
∗
As q1 is the final state. ∴ r= (0 + 1(1 + 01)∗ 00)
Department of Computer Science and Engineering RE December 8, 2025 20/68
 Regular Expression

Arden’s Theorem

Consider the transition system below. Prove that the strings

∗
recognized are (a + a(b + aa)∗ b) a(b + aa)∗ a

Department of Computer Science and Engineering RE December 8, 2025 21/68

 Regular Expression

Arden’s Theorem I
Consider the transition system below. Prove that the strings
∗
recognized are (a + a(b + aa)∗ b) a(b + aa)∗ a

Solution:

q1 = q1 a + q2 b + ∧ (6)
q2 = q1 a + q2 b + q3 a (7)
q3 = q2 a (8)

Department of Computer Science and Engineering RE December 8, 2025 22/68

 Regular Expression

Arden’s Theorem II
Putting equation 8 in equation 7

q2 = q1 a + q2 b + q2 aa
q2 = q1 a + q2 (b + aa)
q2 = q1 a(b + aa)∗

Now putting q2 in equation 6

q1 = q1 a + q2 b + ∧
= q1 a + q1 a(b + aa)∗ b + ∧
= q1 (a + a(b + aa)∗ b) + ∧
∗
= ∧(a + a(b + aa)∗ b)
∗
= (a + a(b + aa)∗ b)

putting this in q2

Department of Computer Science and Engineering RE December 8, 2025 23/68

 Regular Expression

Arden’s Theorem III

∗
q2 = (a + a(b + aa)∗ b) a + q2 b + q2 aa
∗
= (a + a(b + aa)∗ b) a + q2 (b + aa)
∗
= (a + a(b + aa)∗ b) a(b + aa)∗

putting q2 in q3
∗
q3 = (a + a(b + aa)∗ b) a(b + aa)∗ a (9)

Since q3 is the final state.

∗
∴ r= (a + a(b + aa)∗ b) a(b + aa)∗ a

Department of Computer Science and Engineering RE December 8, 2025 24/68

 Regular Expression

Arden’s Theorem I
Prove that the finite automaton whose transition diagram
below accepts the set of all strings over alphabet {a,b} with
an equal number of a’s and b’s, such that each prefix has
atmost one more a than the b’s and atmost one more b than
the a’s

Department of Computer Science and Engineering RE December 8, 2025 25/68

 Regular Expression

Arden’s Theorem II
Solution:

q1 = q2 b + q3 a + ∧ (10)
q2 = q1 a (11)
q3 = q1 b (12)
q4 = q2 a + q3 b + q4 a + q4 b (13)

putting q2 and q3 in q1

q1 = q1 ab + q1 ba + ∧
q1 = q1 (ab + ba) + ∧

applying Arden’s theorem

q1 = ∧(ab + ba)∗
q1 = (ab + ba)∗
Department of Computer Science and Engineering RE December 8, 2025 26/68
 Regular Expression

Arden’s Theorem III

Now, the prefix can be even or odd in length. For Prefix x of
even length, the number of a’s and b’s shall be equal as x is a
substring formed by ab’s and ba’s. For prefix x of odd length,
then we can write ’x’ as ya or yb. As y has even number of
symbols, which implies x has one more a than b or vice-versa

Department of Computer Science and Engineering RE December 8, 2025 27/68

 Regular Expression

Arden’s Theorem

Describe in English the set accepted by finite automaton

whose transition diagram is as under:

Department of Computer Science and Engineering RE December 8, 2025 28/68

 Regular Expression

Arden’s Theorem

Construct a regular expression corresponding to the state

diagram described as under:

Give R.E. for representing the set L of strings in which every 0

is immediately followed by atleast two 1’s. Prove that R.E. r=
∗
∧ + 1∗ (011)∗ (1∗ (011)∗ ) also describes the same set of strings.
Prove
(1 + 00∗ 1) + (1 + 00∗ 1)(0 + 10∗ 1)∗ (0 + 10∗ 1) = 0∗ 1(0 + 10∗ 1)∗

Department of Computer Science and Engineering RE December 8, 2025 29/68

 Two way finite automata

2-way DFA

2-way DFA allows the read head to move left or right on the
input
Two end-markers
Needs only 1 accept or reject state.
A tuple M = {Q, Σ, ⊢, ⊣, δ, s, t, r }
where Q is the set of states
Σ is the input alphabet set
⊢ is the left end marker
⊣ is the right end marker
δ is Q × (Σ ∪ {⊢, λ}) → Q × {L, R}
s is start state
t is the accept state
r is reject state such that r ̸= t

Department of Computer Science and Engineering RE December 8, 2025 30/68

 Two way finite automata

2-Way DFA
Determine the acceptability of 101001 for the following:
State/ Σ 0 1
→ q0 (q0 ,R) (q1 , R)
q1 (q1 ,R) (q2 , L)
q2 (q0 ,R) (q2 , L)
where Q={q0 , q1 , q2 }, s=q0 , t=q1 , r=q2

Department of Computer Science and Engineering RE December 8, 2025 31/68

 Two way finite automata

Transition System containing ∧-moves

Conversion from system with ∧-moves into equivalent system

without ∧-moves
Suppose we want to replace a ∧-move from v1 → v2 , then use the
following steps:
1 Find all edges starting from v2
2 Duplicate all those edges starting from v1 without changing
edge labels.
3 If v1 is initial state, make v2 as Initial state.
4 If v2 is final state, make v1 as final state.

Department of Computer Science and Engineering RE December 8, 2025 32/68

 Two way finite automata

Conversion from system with ∧-moves into

equivalent system without ∧-moves
Consider a finite automaton with ∧-moves given below. Obtain
equivalent automaton without ∧-moves.

Department of Computer Science and Engineering RE December 8, 2025 33/68

 Two way finite automata

Conversion from system with ∧-moves into

equivalent system without ∧-moves
Consider a finite automaton with ∧-moves given below. Obtain
equivalent automaton without ∧-moves.

Department of Computer Science and Engineering RE December 8, 2025 33/68

 Two way finite automata

Conversion from system with ∧-moves into

equivalent system without ∧-moves
Consider a finite automaton with ∧-moves given below. Obtain
equivalent automaton without ∧-moves.

Department of Computer Science and Engineering RE December 8, 2025 33/68

 Two way finite automata

Conversion from system with ∧-moves into

equivalent system without ∧-moves
Consider a finite automaton with ∧-moves given below. Obtain
equivalent automaton without ∧-moves.

Department of Computer Science and Engineering RE December 8, 2025 33/68

 Two way finite automata

Conversion from system with ∧-moves into

equivalent system without ∧-moves

Consider the given transition system containing ∧-move. Obtain

an equivalent transition system without ∧-moves.

Department of Computer Science and Engineering RE December 8, 2025 34/68

 Two way finite automata

Conversion from system with ∧-moves into

equivalent system without ∧-moves

Consider the given transition system containing ∧-move. Obtain

an equivalent transition system without ∧-moves.

Department of Computer Science and Engineering RE December 8, 2025 34/68

 Two way finite automata

Construction of FA equivalent to given RE I

Construct FA equivalent to Regular Expression.
(0 + 1)∗ (00 + 11)(0 + 1)∗
Solution:

Department of Computer Science and Engineering RE December 8, 2025 35/68

 Two way finite automata

Construction of FA equivalent to given RE II

State/Σ 0 1
q0 q0 , q3 q0 , q4
q3 qf
q4 qf
qf qf qf

Department of Computer Science and Engineering RE December 8, 2025 36/68

 Two way finite automata

Construction of FA equivalent to given RE III

converting to DFA
State/Σ 0 1
q0 q0 , q3 q0 , q4
q0 , q3 q0 , q3 , qf q0 , q4
q0 , q4 q0 , q3 q0 , q4 , qf
q0 , q3 , qf q0 , q3 , qf q0 , q4 , qf
q0 , q4 , qf q0 , q3 , qf q0 , q4 , qf
reducing
State/Σ 0 1
q0 q0 , q3 q0 , q4
q0 , q3 q0 , q3 , qf q0 , q4
q0 , q4 q0 , q3 q0 , q3 , qf
q0 , q3 , qf q0 , q3 , qf q0 , q3 , qf

Department of Computer Science and Engineering RE December 8, 2025 37/68

 Two way finite automata

Construction of FA equivalent to given RE

1 Construct DFA with reduced states equivalent to R.E.

(10+(0+11)0∗ 1).
2 Construct transition system equivalent to R.E.
(ab + c ∗ )∗ b
a + bb + bab ∗ a
(a + b)∗ abb
3 Prove that
(a∗ ab + ba)∗ a∗ = (a + ab + ba)∗
4 Construct a finite automata accepting all strings over {0,1}
ending in 010 or 0010.
5 Construct a regular grammar which can generate the set of all
strings starting with a letter (A to Z) followed by a string of
letters or digits (0 to 9).

Department of Computer Science and Engineering RE December 8, 2025 38/68

 Pumping Lemma for Regular Sets

Pumping Lemma for Regular Sets

Let M = (Q, Σ, δ, q0 , F) be a finite automaton with ’n’

states. Let L be the regular sets accepted by M.
Let w ∈ L and |w |≥ m, if m ≥ n, then ∃ x,y,z such that
w=xyz, y ̸= ∧ and xy i z ∈ L for each i ≥ 0.
Applications of Pumping Lemma: Used to prove that
certain set are not regular.
Steps to prove that given set is not regular:
1 Assume L is regular. Let ’n’ be the number of states in
corresponding FA.
2 Choose a string ’w’ such that |w |≥ n. Use pumping lemma to write
w=xyz with |xy |≤ n and |y |> 0
3 Find a suitable integer i such that xy i z ̸∈ L. This contradicts our
assumption. Hence, L is not regular.

Department of Computer Science and Engineering RE December 8, 2025 39/68

 Pumping Lemma for Regular Sets

Pumping Lemma for Regular Sets

2
Show that the set L ={ai |i ≥ 1} is not regular
Solution:
Let L is regular
Let ’n’ be number of states in FA accepting L.
Let w=an2 =⇒ |w |= n2 > n
by pumping lemma, w=xyz with |xy |≤ n and |y |> 0
Consider xy 2 z
|xy 2 z |= |x |+ 2 |y |+ |z |> |x |+ |y |+ |z |∵ |y |> 0
=⇒ n2 = |xyz |= |x |+ |y |+ |z |< |xy 2 z |
As |xy |≤ n, |y |≤ n
∴ |xy 2 z |= |x |+ 2 |y |+ |z |≤ n2 + n < n2 + n + n + 1.
Hence, |xy 2 z |lies between n2 and (n + 1)2 but not equal to
any one of them.
∴ |xy 2 z |is not a perfect square and so xy 2 z ̸∈ L.
∴ this is a contradiction. This implies not Regular
Department of Computer Science and Engineering RE December 8, 2025 40/68
 Pumping Lemma for Regular Sets

Pumping Lemma for Regular Sets

Show that L= {ap |p is a prime} is not regular. Solution:

1 Let L is regular. Let ’n’ be number of states in finite
automata accepting L.
2 Let ’p’ be a prime number greater than ’n’.
Let w=ap
by pumping lemma, w=xyz with |xy |≤ n and |y |> 0
x, y, z are simply strings of a’s.
So, y= am for some m ≥ 1 (and ≤ n)
3 Let i= p+1, then
|xy i z |= |xyz |+ |y i−1 |=p+(i-1)m=p+pm=p(1+m) which is
not prime.
∴ xy i z ̸∈ L. =⇒ contradiction.
So, L is not regular.

Department of Computer Science and Engineering RE December 8, 2025 41/68

 Pumping Lemma for Regular Sets

Pumping Lemma for Regular Sets

1 Show that L={0i 1i |i ≥ 1} is not regular.

2 Show that L= {ww |w ∈ {a, b}∗ } is not regular.
3 Is L = {a2n |n ≥ 1} regular ?

Department of Computer Science and Engineering RE December 8, 2025 42/68

 Pumping Lemma for Regular Sets

Regular Sets and Regular Grammar

Construct a regular grammar G generating the regular set
represented by
P= a∗ b(a + b)∗ .

Department of Computer Science and Engineering RE December 8, 2025 43/68

 Pumping Lemma for Regular Sets

Regular Sets and Regular Grammar

Construct a regular grammar G generating the regular set
represented by
P= a∗ b(a + b)∗ .
Solution:

Department of Computer Science and Engineering RE December 8, 2025 43/68

 Pumping Lemma for Regular Sets

Regular Sets and Regular Grammar

Construct a regular grammar G generating the regular set
represented by
P= a∗ b(a + b)∗ .
Solution:

Let G=({q0 , q1 },{a,b},P,q0 )

where P is given by:

Department of Computer Science and Engineering RE December 8, 2025 43/68

 Pumping Lemma for Regular Sets

Regular Sets and Regular Grammar

Construct a regular grammar G generating the regular set
represented by
P= a∗ b(a + b)∗ .
Solution:

Let G=({q0 , q1 },{a,b},P,q0 )

where P is given by:
q0 → aq0
q0 → bq1 , q0 → b
q1 → aq1 , q1 → bq1
q1 → b
q1 → a

Department of Computer Science and Engineering RE December 8, 2025 43/68

 Pumping Lemma for Regular Sets

Regular Sets and Regular Grammar

Construct a regular grammar G generating the regular set
represented by
P= a∗ b(a + b)∗ .
Solution:

Let G=({q0 , q1 },{a,b},P,q0 )

where P is given by:
q0 → aq0
q0 → bq1 , q0 → b
q1 → aq1 , q1 → bq1
q1 → b
q1 → a
Let G=({A,B},{a,b},P,A) where P consists of
A → aB, B → bB
B → b, B → bA
Construct a transition system M accepting
Department of Computer Science and Engineering RE
L(G).December 8, 2025 43/68
 Pumping Lemma for Regular Sets

Regular Sets and Regular Grammar

If a regular grammar G is given by S → aS |a. Find M

accepting L(G).
Construct a DFA equivalent to grammar
S → aS |bS |aA
A → bB
B → aC, C → ∧

Department of Computer Science and Engineering RE December 8, 2025 44/68

 My-Hill-Nerode Theorem

My-hill Nerode Theorem I

Used for Minimization of DFA.
Steps:
1 Draw a table for all pair of states (P,Q).
2 Mark all pairs where P ∈ F and Q ̸∈ F.
3 IF there are unmarked pairs (P,Q) such that [δ(P, X ), δ(Q, X )] is
marked, then mark [P,Q], where ’X’ is an input symbol.
4 Repeat step 3 untill no more marking can be made.
5 Combine all un-marked pairs and make them a single state in
minimized DFA.
Minimize the given deterministic finite automata

Department of Computer Science and Engineering RE December 8, 2025 45/68

 My-Hill-Nerode Theorem

My-hill Nerode Theorem II

Solution:

Department of Computer Science and Engineering RE December 8, 2025 46/68

 My-Hill-Nerode Theorem

My-hill Nerode Theorem III

(B,A) =⇒ δ(B, 0) = A
δ(A, 0) = B Unmarked
δ(B, 1) = D
δ(A, 1) = C unmarked
(D,C) =⇒ δ(D, 0) = E
δ(D, 0) = E Unmarked
δ(C , 1) = F
δ(C , 1) = F unmarked
(E,C) =⇒ δ(E , 0) = E
δ(C , 0) = E Unmarked
δ(E , 1) = F
δ(C , 1) = F unmarked
(E,D) =⇒ δ(E , 0) = E
δ(E , 0) = E Unmarked
δ(D, 1) = F

Department of Computer Science and Engineering RE December 8, 2025 47/68

 My-Hill-Nerode Theorem

My-hill Nerode Theorem IV

δ(D, 1) = F unmarked
(F,A) =⇒ δ(F , 0) = F
δ(A, 0) = B Unmarked
δ(F , 1) = F
δ(A, 1) = C Marked, Mark (F,A)
(F,B) =⇒ δ(F , 0) = F
δ(B, 0) = A Marked, Mark (F,B)
δ(F , 1) = F
δ(B, 1) = D Marked, Mark (F,B)

Department of Computer Science and Engineering RE December 8, 2025 48/68

 My-Hill-Nerode Theorem

My-hill Nerode Theorem V

Therefore, unmarked pairs:

(A,B),(D,C),(E,C),(E,D)
here, (C,D,E) form a common pair. So, combined state
(C,D,E)
States 0 1
{A,B} {A,B} {C,D,E}
{C,D,E} {C,D,E} {F}
{F} {F} {F}

Department of Computer Science and Engineering RE December 8, 2025 49/68

 My-Hill-Nerode Theorem

My-hill Nerode Theorem VI

Department of Computer Science and Engineering RE December 8, 2025 50/68

 Finite Automata with Output

Finite Automata with Outputs

Moore Machine is a 6-tuple (Q,Σ, ∆, δ, λ, q0 )
where Q is a finite set of states
Σ is the input alphabet
∆ is the output alphabet
δ is the transition function Q × Σ into Q
λ is the output function Q into ∆
q0 is the initial state

Department of Computer Science and Engineering RE December 8, 2025 51/68

 Finite Automata with Output

Finite Automata with Outputs

Moore Machine is a 6-tuple (Q,Σ, ∆, δ, λ, q0 )
where Q is a finite set of states
Σ is the input alphabet
∆ is the output alphabet
δ is the transition function Q × Σ into Q
λ is the output function Q into ∆
q0 is the initial state

Example:
Initial state q0 is marked with an arrow. The table defines δ and λ:

Present Next State Output

State a=0 a=1 λ
→○ q0 q3 q1 0
q1 q1 q2 1
q2 q2 q3 0
q3 q3 q0 0

Determine transition states and output string for input string 0111.

Department of Computer Science and Engineering RE December 8, 2025 51/68

 Finite Automata with Output

Finite Automata with Outputs

Moore Machine is a 6-tuple (Q,Σ, ∆, δ, λ, q0 )
where Q is a finite set of states
Σ is the input alphabet
∆ is the output alphabet
δ is the transition function Q × Σ into Q
λ is the output function Q into ∆
q0 is the initial state

Example:
Initial state q0 is marked with an arrow. The table defines δ and λ:

Present Next State Output

State a=0 a=1 λ
→○ q0 q3 q1 0
q1 q1 q2 1
q2 q2 q3 0
q3 q3 q0 0

Determine transition states and output string for input string 0111.
Solution: Transition states:
0\0 1\0 1\0 1\1
q0 −−→ q3 −−→ q0 −−→ q1 −−→ q2 0
OutputString: 00010

Department of Computer Science and Engineering RE December 8, 2025 51/68

 Finite Automata with Output

Finite Automata with Outputs

Mealy Machine is a 6-tuple (Q,Σ, ∆, δ, λ, q0 )
where Q is a finite set of states
Σ is the input alphabet
∆ is the output alphabet
δ is the transition function Q × Σ into Q
λ is the output function mapping Q ×Σ into ∆
q0 is the initial state

Department of Computer Science and Engineering RE December 8, 2025 52/68

 Finite Automata with Output

Finite Automata with Outputs

Mealy Machine is a 6-tuple (Q,Σ, ∆, δ, λ, q0 )
where Q is a finite set of states
Σ is the input alphabet
∆ is the output alphabet
δ is the transition function Q × Σ into Q
λ is the output function mapping Q ×Σ into ∆
q0 is the initial state

Example:
Consider a mealy machine for q1 as initial state.

Present a=0 a=1

State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

Determine the transition of states and corresponding output string for input string
0011.

Department of Computer Science and Engineering RE December 8, 2025 52/68

 Finite Automata with Output

Finite Automata with Outputs

Mealy Machine is a 6-tuple (Q,Σ, ∆, δ, λ, q0 )
where Q is a finite set of states
Σ is the input alphabet
∆ is the output alphabet
δ is the transition function Q × Σ into Q
λ is the output function mapping Q ×Σ into ∆
q0 is the initial state

Example:
Consider a mealy machine for q1 as initial state.

Present a=0 a=1

State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

Determine the transition of states and corresponding output string for input string
0011.
0\0 0\1 1\0 1\0
Solution: q1 −−→ q3 −−→ q2 −−→ q4 −−→ q3
Output String: 0100

Department of Computer Science and Engineering RE December 8, 2025 52/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

Department of Computer Science and Engineering RE December 8, 2025 53/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:

Department of Computer Science and Engineering RE December 8, 2025 53/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1
q20
q21
q3
q40
q41
Department of Computer Science and Engineering RE December 8, 2025 53/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3 q21

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3 q21 1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3 q21 1 q1

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3 q21 1 q1 1
q40

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3 q21 1 q1 1
q40 q41

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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

Department of Computer Science and Engineering RE December 8, 2025 54/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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
Department of Computer Science and Engineering RE December 8, 2025 54/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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
Department of Computer Science and Engineering RE December 8, 2025 54/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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
Department of Computer Science and Engineering RE December 8, 2025 54/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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
Department of Computer Science and Engineering RE December 8, 2025 54/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1
State State Output 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
Department of Computer Science and Engineering RE December 8, 2025 54/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20
q20 q1 q40
q21 q1 q40
q3 q21 q1
q40 q41 q3
q41 q41 q3

Department of Computer Science and Engineering RE December 8, 2025 55/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20 1
q20 q1 q40
q21 q1 q40
q3 q21 q1
q40 q41 q3
q41 q41 q3

Department of Computer Science and Engineering RE December 8, 2025 56/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40
q3 q21 q1
q40 q41 q3
q41 q41 q3

Department of Computer Science and Engineering RE December 8, 2025 57/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40 1
q3 q21 q1
q40 q41 q3
q41 q41 q3

Department of Computer Science and Engineering RE December 8, 2025 58/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40 1
q3 q21 q1 0
q40 q41 q3
q41 q41 q3

Department of Computer Science and Engineering RE December 8, 2025 59/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40 1
q3 q21 q1 0
q40 q41 q3 0
q41 q41 q3

Department of Computer Science and Engineering RE December 8, 2025 60/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a

moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40 1
q3 q21 q1 0
q40 q41 q3 0
q41 q41 q3 1

Department of Computer Science and Engineering RE December 8, 2025 61/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Consider the mealy machie described by given transition table. Construct a
moore machine which is equivalent to given mealy machine.
Present a=0 a=1
State State Output State Output
→ q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0

q20 q40

q2 q4

q21 q41
Solution:
Present a=0 a=1 Output
→ 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
Department of Computer Science and Engineering RE December 8, 2025 62/68
 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Convert the given mealy machine into equivalent moore machine

Department of Computer Science and Engineering RE December 8, 2025 63/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Convert the given mealy machine into equivalent moore machine

Department of Computer Science and Engineering RE December 8, 2025 63/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Convert the given mealy machine into equivalent moore machine

Department of Computer Science and Engineering RE December 8, 2025 63/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Convert the given mealy machine into equivalent moore machine

Department of Computer Science and Engineering RE December 8, 2025 63/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Present a=0 a=1

State state Output State Output
→ q1 q2 Z1 q3 Z1
q2 q2 Z2 q3 Z1
q3 q2 Z1 q3 Z2

Department of Computer Science and Engineering RE December 8, 2025 64/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Present a=0 a=1

State state Output State Output
→ q1 q2 Z1 q3 Z1
q2 q2 Z2 q3 Z1
q3 q2 Z1 q3 Z2

q21 q31
q2 q3
q22 q32

Department of Computer Science and Engineering RE December 8, 2025 64/68

 Finite Automata with Output

Procedure of transforming Mealy machine into Moore machine

Present a=0 a=1

State state Output State Output
→ q1 q2 Z1 q3 Z1
q2 q2 Z2 q3 Z1
q3 q2 Z1 q3 Z2

Present a=0 a=1

q21 q31 State state Output State Output
q1 q21 Z1 q31 Z1
q2 q3 q21 q22 Z2 q31 Z1
q22 q22 Z2 q31 Z1
q22 q32 q31 q21 Z1 q32 Z2
q32 q21 Z1 q32 Z2

Department of Computer Science and Engineering RE December 8, 2025 64/68

 Finite Automata with Output

Procedure of transforming Mealy machine into

Moore machine
Present Next State Output
State a=0 a=1
q1 q21 q31
q21 q22 q31 Z1
q22 q22 q31 Z2
q31 q21 q32 Z1
q32 q21 q32 Z2

Department of Computer Science and Engineering RE December 8, 2025 65/68

 Finite Automata with Output

Procedure of transforming Moore machine into Mealy machine

Consider the moore machine described by the transition table given:

Present Next State Output
State a=0 a=1
→ q1 q1 q2 0
q2 q1 q3 0
q3 q1 q3 1
Construct the corresponding mealy machine.

Department of Computer Science and Engineering RE December 8, 2025 66/68

 Finite Automata with Output

Procedure of transforming Moore machine into Mealy machine

Consider the moore machine described by the transition table given:

Present Next State Output
State a=0 a=1
→ q1 q1 q2 0
q2 q1 q3 0
q3 q1 q3 1
Construct the corresponding mealy machine.
Solution:
Present a=0 a=1
State state Output State Output
→ q1 q1 0 q2 0
q2 q1 0 q3 1
q3 q1 0 q3 1

Department of Computer Science and Engineering RE December 8, 2025 66/68

 Finite Automata with Output

Procedure of transforming Moore machine into Mealy machine

Consider the moore machine described by the transition table given:

Present Next State Output
State a=0 a=1
→ q1 q1 q2 0
q2 q1 q3 0
q3 q1 q3 1
Construct the corresponding mealy machine.
Solution:
Present a=0 a=1
State state Output State Output
→ q1 q1 0 q2 0
q2 q1 0 q3 1
q3 q1 0 q3 1
Now, Find identical rows and remove one of them

Department of Computer Science and Engineering RE December 8, 2025 66/68

 Finite Automata with Output

Procedure of transforming Moore machine into Mealy machine

Consider the moore machine described by the transition table given:

Present Next State Output
State a=0 a=1
→ q1 q1 q2 0
q2 q1 q3 0
q3 q1 q3 1
Construct the corresponding mealy machine.
Solution:
Present a=0 a=1
State state Output State Output
→ q1 q1 0 q2 0
q2 q1 0 q3 1
q3 q1 0 q3 1
Now, Find identical rows and remove one of them
Present a=0 a=1
State state Output State Output
→ q1 q1 0 q2 0
q2 q1 0 q2 1

Department of Computer Science and Engineering RE December 8, 2025 66/68

Questions?
vnehra@[Link]
Thank you.