Module-2

Finite Automata

12/23/2025
1
Language Recognizers : An example of
Finite Automata

An automaton is an abstract model of a

digital computer.

Finite Automata(FA) is the simplest

machine to recognize patterns.

12/23/2025 2
Finite Automaton

Input
String
Output
“Accept”
Finite or
Automaton “Reject”

12/23/2025
3
Representation of Finite Automata

Finite Automata is represented by –

1. Transition Graph
2. Transition Table
3. Regular Expression

12/23/2025 4
Transition Graph
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

initial accepting
state state state
transition

12/23/2025 Dakhole Dipali K

5
Initial Configuration
Input String
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

6
Reading the Input

a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

7
 a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

8
 a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

9
 a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

10
 Input finished

a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

accept
12/23/2025 Dakhole Dipali K 11
Rejection

a b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

12
 a b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

13
 a b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

14
 a b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

15
 Input finished

a b a

a, b

reject
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K 16

Another Rejection

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

12/23/2025 Dakhole Dipali K

17
 

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

reject
12/23/2025 Dakhole Dipali K
18
Another Example

a a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 19

 a a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 20

 a a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 21

 a a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 22

 Input finished

a a b

a a, b
accept

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 23

Rejection Example

b a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 24

b a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 25

b a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 26

b a b

a a, b

b a, b
q0 q1 q2

12/23/2025 Dakhole Dipali K 27

 Input finished

b a b

a a, b

b a, b
q0 q1 q2

reject
12/23/2025 Dakhole Dipali K 28
Languages Accepted by FAs
Definition:

The languageLM  contains

all input strings accepted byM

LM  = { strings that bring

M
to an accepting state}

12/23/2025 Dakhole Dipali K

29
Example
LM  abba M

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

accept
12/23/2025 Dakhole Dipali K
30
Example
LM   , ab, abba M

a, b

q5
b a a a, b
b
q0 a q1 b q2 b q3 a q4

accept accept accept

12/23/2025 Dakhole Dipali K
31
Example

n
LM  {a b : n 0}

a a, b

b a, b
q0 q1 q2
trap state/
accept
dead state
12/23/2025 Dakhole Dipali K
32
Formal Definition
• Finite Automaton (FA)

M Q, ,  , q0 , F 
Q : set of states
 : input alphabet
 : transition function
q0 : initial state
F : set of accepting states
33
Input Alphabet 
 a, b
•

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

34
Set of States Q
Q q0 , q1, q2 , q3 , q4 , q5 
•

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

35
Initial State q0

•
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

36
Set of Accepting States F
F q4 
•
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

37
Transition Function 

•
 : Q   Q

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

38
  q0 , a  q1

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

39
  q0 , b  q5

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

40
  q2 , b  q3

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

41
 Transition Table 
 a b
q0 q1 q5
•
q1 q5 q2
q2 q5 q3
q3 q4 q5 a, b

∗𝑞 4 q5 q5
q5
𝑞5 q5 q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
42
Extended Transition Function  *

•
 * : Q *  Q

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

43
  * q0 , ab  q2

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

44
  * q0 , abba  q4

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

45
  * q0 , abbbaa  q5

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

46
Observation: if there is a walk from q to q
with label w then

 * q, w q

q w q

w  1 2  k
1 2 k
q q
47
Example: There is a walk from q0 to q5
with label abbbaa

 * q0 , abbbaa  q5

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

48
 Recursive Definition
 * q,   q
 * q, w   ( * (q, w), )

q w q1  q

 * q, w  q
 * q, w   (q1, )
 (q1, ) q
 * q, w   ( * (q, w), )
 * q, w q1

49
 * q0 , ab 
  * (q0 , a),b  
   * q0 ,  , a , b  
  q0 , a , b  
 q1, b  
q2 a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
50
Check the string acceptance of abba
• δ*(qo,abba)= δ(δ*(q0,abb) , a)
• = δ(δ (δ*(q0,ab),b) , a)
• = δ(δ (δ (δ*(q0,a),b),b) , a)
• = δ(δ (δ (δ (δ*(q0,λ),a),b),b) , a)
• = δ(δ (δ (δ (q0,a),b),b) , a)
• =δ(δ (δ (q1,b),b) , a)
• =δ(δ (q2,b) , a)
• =δ(q3, a)
• =q4 Є F
• String abba is accepted as q4 is a final state

51
 Language Accepted by FAs
• For a FA M Q, ,  , q0 , F 
• Language accepted by :
M
•
LM  w  * :  * q0 , w F 

q0 w q q F

52
Example
LM= { all strings with prefix ab }
• a, b

q0 a q1 b q2

b a accept

q3 a, b
53
L=strings with substring ‘101’
over {0, 1}

54
Example
LM = { all strings without
• substring 001 }

1 0 0,1
1

 0 1
0 00 001

0
55
Example
L( M ) awa : w  a, b *
a
b
•
b
q0 a q2 q3

b a
q4

a, b 56
Regular Languages

• Definition: L
M
• A language is regular  
L Lif there
M is
• FA such that

• Observation:
• All languages accepted by FAs
• form the family of regular languages
•

57
Examples of regular languages:

abba  , ab, abba

awa : w  a, b * {a nb : n 0}
{ all strings with prefix ab }
{ all strings without substring 001 }
There exist automata that accept these
Languages

58
 here exist languages which are not Regular:

n n
Example: L{a b : n 0}

There is no FA that accepts such a language

(we will prove this later in the class)

59
 Deterministic Finite Automata
• Every State should have transition over every
input symbol
• There should be only One next state for each
transition
• DFA is defined as

M Q, ,  , q0 , F 

12/23/2025
60
 DFA Example
Design DFA that accepts language L= { w : |w| mod 3 = 0 }
over ∑ = {a, b}
Solution
Strings accepted= {ϵ, aaa, bbb, aba, aab, bab, aaabbb,
ababab, …}
Strings rejected= {a, b, ab, ba, abab, baba, bbaa, aaabb, …}
Transition Diagram

q0 a, b q1 a, b q4
a, b

12/23/2025
61
 DFA Example
Consider Sample String : aab

a, b
q0 q1 a, b q4
a, b

12/23/2025
62
 DFA Example
Consider Sample String : aab

a, b q a, b
q0 1 q4
a, b

12/23/2025
63
 DFA Example
Consider Sample String : aab

q0 a, b q a, b q4
1
a, b

12/23/2025
64
 DFA Example
Consider Sample String : aab
 String is accepted

Acceptance State

q0 a, b q a, b q4
1

a, b

12/23/2025
65
 DFA Example
Consider Another Sample String : baba

a, b
q0 q1 a, b q4
a, b

12/23/2025
66
 DFA Example
Consider Another Sample String : baba

a, b q a, b
q0 1 q4
a, b

12/23/2025
67
 DFA Example
Consider Another Sample String : baba

q0 a, b q a, b q4
1
a, b

12/23/2025
68
 DFA Example
Consider Another Sample String : baba

q0 a, b q a, b q4
1

a, b

12/23/2025
69
 DFA Example
Consider Another Sample String : baba
 String is rejected

Rejection State

q0 a, b q a, b q4
1

a, b

12/23/2025
70
 DFA Example
DFA Tuples M=(Q, Σ, , q0, F)
 Q= {q0, q1, q4}
 Σ= {a, b}
 = Transition function represented by Transition
table
 q0= Initial State
F= {q0}  Acceptance State

12/23/2025
71
 DFA Example
Transition Table

Q
Σ a b
*q0 q1 q1
q1 q4 q4
q4 q0* q0*

12/23/2025
72
DFA Examples to be covered

12/23/2025 Dakhole Dipali K

73
DFA - Starts with a , ∑={a,b}
• L= { a,aa,ab,aaa,aab,aba,….}
a,b

a
q q
0 1

b
q
2
a,b 74
DFA - Starts with ab , ∑={a,b}
• L= { ab,aba,abb,….}

a,b
a b
q q q
0 1 2
b a
q
3
a,b
75
DFA - Starts with aa , ∑={a,b}
• L = { aa,aab,aaba,….}

a,
b
a a
q q q
0 1 2
b
b
q
3 a,b
76
 DFA - Starts with aba , ∑={a,b}
• L={ aba,abaa,abab,abaaa,…}

a,b
a b a
q q q q
0 1 2 3
a
b b

q
4 a,b
77
DFA - Starts with 101 , ∑={0,1}
• L={ 101,1010,1011,101101,…}

0,1
1 1
q q q q
0 1 2 3
1
0 0

q
4 0,1
78
78
Ends with a
• L={a,aa,ba,aaa,aba,…}
b a

a q1
q0

79
• L={ 1,01,11,…}

0 1

1
q0 q1

80
 Ends with ab
• L={ab,aab,bab,aaab,bbbbab,abab,…}

b a

a b
q0 q1 q2
a

81
Ending with bab
b
a
b

q0 b q1 a b
q2 q3

a
a

82
82
DFA – Ends with 101, ∑={ 0,1}
• L={ 101,0101,1101,000101,111101,…}
1
0 1 0

0 1
1 q1 q3
q0 q2

83
DFA – Ends with 111 , ∑={ 0,1}
• L= { 111,0111,11111,…}
0
0 1
1 1
1 q1 q2 q3
q0

0 0

84
 DfA – Substring 101
• L={ 101,0101,1101,1010,1011,00010111,…}

0 1 0,1

1 0 1
q0 q1 q2 q3

85
 DFA- Contains 111
• L={ 111,0111,1111,000111000,11111000,..}

0 0,
1
1 1 1
q0 q1 q2 q3

0
0

86
 DFA – Contains 1011
• L= { 1011,01011,11011,00010111,..}

0 1 0,1

0 1 1
1
q0

0 0

87
DFA- Even no of 0s, ∑={ 0,1} or
n0(w)mod2=0
• L={ λ,
1,1111,00,0000,11100,1110000,0000111,..}
1 1

0
q0 q1
Transitio o 1
n
*->q0 q1 q0
0 q1 qo q1

88
DFA – Odd no of 0’s , ∑={ 0,1} or
n0(w)mod2=1
• L={ 0,01,1110,000,000001111,…}
1 1

0
q0 q1

89
 DFA
L={ - na(w)mod3=0, ∑={ a,b}
λ,bbbb,aaabbb,aaaaaabbb,
….}
b b b

a a

90
DFA- nb(w)mod4=1, ∑={ a,b}
a a a
a

b b b

91
DfA – n1(w)mod3=2, ∑={ 0,1}
0 0 0

1 1

92
Dfa –lwlmod2=0,

a,b

a,b

93
DfA – lwlmod2=1
L={a,b,aaa,aba,aab,baa,bbb
,baba,bba,….

a,b

a,b

94
DFA –lwlmod3=0, ∑={ 0,1}

a,b a,b

a,b

95
No of a’s is even and no of b’s odd-
eo
a

ee a oe

b b b b

a
eo oo

a 96
No of a’s is odd and no of b’s
even=oe
a

ee a oe

b b b b

a
eo oo

a 97
No of a’s is odd and no of b’s odd-oo
a

ee a oe

b b b b

a
eo oo

a 98
No of a’s is even and no of b’s even-
ee
a

ee a oe

b b b b

a
eo oo

a 99
 NFA Definition
NFA is defined as M=(Q, ∑ , ꝺ, q0, F)
Where, Q= set of states
Σ = input alphabet
ꝺ = transition function ꝺ: Q X ( Σ ) 
q0 Start / Initial State
F  set of acceptance state

a, b q1 b q2
a
q0
b q3 a q4

12/23/2025
100
 NFA Example
Design NFA that accepts language of strings ending with
ab/ba over ∑ = {a, b}
Solution
Strings accepted= {ab, ba, abab, baba, bbab, aaaba, …}
Strings rejected= {ϵ, a, b, aa, bb, aaa, abb, aaabbb, …}
Transition Diagram

a, b q1 b q2
a
q0
b q3 a q4

12/23/2025
101
 NFA to DFA Conversion Example
Convert NFA to DFA that accepts language of strings ending
with ab/ba over ∑ = {a, b}
Solution
Draw NFA for given language
Convert that NFA into DFA using subset construction method

a, b q1 b q2
a
q0
b q3 a q4

12/23/2025
102
NFA to DFA Conversion Example
 Using LConstruction Method NFA a b
 Consider {q0} as Start State q0 {q0, q1} {q0, q3}
 (q0, a)={q0 q1} newly formed state
 ({q0 q1}, a)= (q0, a)ᴜ ({q1, a}) q1 - {q2}
={q0, q1} ᴜ {Ø} q2 - -
={q0 q1} q3 {q4} -
 ({q0 q1}, b)= (q0, b)ᴜ ({q1, b})
={q0, q3} ᴜ {q2} q4 - -
={q0 q2 q3}
DFA a b
q0 {q0 q1} {q0 q3}
{q0 q1} {q0 q1} {q0 q2 q3}

12/23/2025
103
 NFA to DFA Conversion Example
 Using Lazy Evaluation Method NFA a b

𝜹(q0, a)={q0 q1} newly formed state

 Consider {q0} as Start State q0 {q0, q1} {q0, q3}
𝜹({q0 q1}, a)= 𝜹(q0, a)ᴜ 𝜹({q1, a})

 q1 - {q2}
={q0, q1} ᴜ {Ø} q2 - -

𝜹({q0 q1}, b)= 𝜹(q0, b)ᴜ 𝜹({q1, b})

={q0 q1} q3 {q4} -

={q0, q3} ᴜ {q2} q4 - -
={q0 q2 q3}
DFA a b
𝜹({q0 q2 q3}, a)= 𝜹(q0, a) ᴜ 𝜹({q2, a}) ᴜ 𝜹({q3,
 {q0 q2 q3} is newly formed state
 q0 {q0 q1} {q0 q3}
a}) {q0 q1} {q0 q1} {q0 q2 q3}
={q0, q1} ᴜ {Ø} ᴜ {q4}
{q0 q2 q3) {q0 q1 q4} {q0 q3}
𝜹({q0 q2 q3}, b)= 𝜹(q0, b)ᴜ 𝜹({q2, b}) ᴜ 𝜹({q3,
={q0 q1 q4}

b})
={q0, q3} ᴜ {Ø} ᴜ {Ø} ={q0 q3}

12/23/2025
104
 NFA to DFA Conversion Example
 𝜹({q0 q3}, a)= 𝜹(q0, a)ᴜ 𝜹({q3, a})
 {q0 q3} is newly formed state NFA a b
q0 {q0, q1} {q0, q3}
={q0, q1} ᴜ {q4}
q1 - {q2}
 𝜹({q0 q3}, b)= 𝜹(q0, b)ᴜ 𝜹({q3, b})
={q0 q1 q4}
q2 - -
={q0, q3} ᴜ {Ø} q3 {q4} -
={q0 q3}
q4 - -

DFA a b
q0 {q0 q1} {q0 q3}
{q0 q1} {q0 q1} {q0 q2 q3}
{q0 q2 q3) {q0 q1 q4} {q0 q3}
{q0 q3} {q0 q1 q4} {q0 q3}

12/23/2025
105
 NFA to DFA Conversion Example
 𝜹({q0 q3}, a)= 𝜹(q0, a)ᴜ 𝜹({q3, a})
 {q0 q3} is newly formed state NFA a b
q0 {q0, q1} {q0, q3}
={q0, q1} ᴜ {q4}
q1 - {q2}
 𝜹({q0 q3}, b)= 𝜹(q0, b)ᴜ 𝜹({q3, b})
={q0 q1 q4}
q2 - -
={q0, q3} ᴜ {Ø} q3 {q4} -
={q0 q3}
q4 - -
 𝜹({q0 q1 q4}, a)= 𝜹(q0, a) ᴜ 𝜹({q1, a}) ᴜ 𝜹({q4, a})
 {q0 q1 q4} is newly formed state
DFA a b
={q0, q1} ᴜ {Ø} ᴜ {Ø}

 𝜹({q0 q1 q4}, b)= 𝜹(q0, b)ᴜ 𝜹({q1, b}) ᴜ 𝜹({q4, b})

={q0 q1} q0 {q0 q1} {q0 q3}
{q0 q1} {q0 q1} {q0 q2 q3}
={q0, q3} ᴜ {q2} ᴜ {Ø}
{q0 q2 q3) {q0 q1 q4} {q0 q3}
={q0 q2 q3}
{q0 q3} {q0 q1 q4} {q0 q3}
{q0 q1 q4} {q0 q1} {q0 q2 q3}

12/23/2025
106
NFA to DFA Conversion Example
DFA a b
q0 {q0 q1} {q0 q3}
{q0 q1} {q0 q1} {q0 q2 q3}
{q0 q2 q3) {q0 q1 q4} {q0 q3}
a
{q0 q3} {q0 q1 q4} {q0 q3}
{q0 q1 q4} {q0 q1} {q0 q2 q3}
q0 q1 b q0 q2 q3
a b
q0 b a
a b
b q0 q3 q0 q1q4
a

12/23/2025
107
 Minimization of DFA Example
Minimize the following DFA
DFA 0 1
A B C
B B D
0
C B C 0
D B E
E* B C 1 D
B
0
0 1
A 1 0
1 1
C E

12/23/2025
108
 Minimization of DFA Example
Minimize the following DFA
Use State Equivalence Method DFA 0 1
Write 0’Equivalence as A B C
{A, B, C, D} {E} B B D
Write 1’Equivalence C B C
D B E
{A, B, C} {D} {E}
E* B C
Write 2’Equivalence
{A, C} {B} {D} {E}
Write 3’Equivalence
{A, C} {B} {D} {E}

12/23/2025
109
 Minimization of DFA Example
Minimize the following DFA DFA 0 1
Use State Equivalence Method A,C B C
Write 0’Equivalence as B B D
D B E
{A, B, C, D} {E}
E* B C
Write 1’Equivalence
{A, B, C} {D} {E} 0 0
Write 2’Equivalence
B
1
D
{A, C} {B} {D} {E}
0
Write 3’Equivalence 1 1
{A, C} {B} {D} {E} 0
A, C 1
E

12/23/2025
110