THEORY OF COMPUTATIONS

Module 2: Finite Automata

1 / 184
Outline

1 Finite Automata

2 An Informal Picture of Finite Automata

3 Deterministic Finite Automata (DFA)

4 Finite Automata with Epsilon-Transitions

5 Minimization of DFA

2 / 184
Introduction of Finite Automata

A finite automaton is a mathematical model of computation that

represents a system with a finite number of states.

It processes input symbols one at a time and transitions between states

according to predefined rules.

The automaton accepts or rejects an input string based on whether it ends

in an accepting state.

Real Time Example

Exampe 1 : Vending Machine

Exampe 2 : Traffic Light

Exampe 3 : Elevator

3 / 184
Example 1: Vending Machine

Formal Representation:
A vending machine FA can be modeled as a 5-tuple:

(Q, Σ, δ, q0 , F)

Q — States: waiting, paid, dispensing

Σ — Inputs: coin insert, select item
δ — Transition function: what next state on input
q0 — Start state: waiting for input
F — Accepting state(s): item dispensed

Real-Time Mapping:
Think of it as a controller:
 
Insert Accept Dispense  Return Change
4 / 184
Vending Machine: Transition Diagram

Problem: Is this sequence accepted?

InsertCoin  SelectItem

q0 (Waiting) –InsertCoin– q1 (Paid)

q1 (Paid) –SelectItem– q2 (Dispensing)

Answer: Accepted

InsertCoin SelectItem
start Waiting Paid Dispensing

5 / 184
Example 2: Traffic Light
Formal Representation:
A traffic light FA can be modeled as a 5-tuple:

(Q, Σ, δ, q0 , F)

Q — States: q0 (Red), q1 (Yellow), q2 (Green),

q3 (Yellow)
Σ — Inputs: Timer tick (t)
δ — Transition function:
δ(q0 , t) = q1
δ(q1 , t) = q2
δ(q2 , t) = q3
δ(q3 , t) = q0
q0 — Start state: Red
F — No final state (continuous cycle)
Real-Time Mapping:

Red Yellow Green  Yellow  Red  . . . 6 / 184
Traffic Light as Finite Automaton

States Description:
q0 (Red): Stop – initial state.
q1 (Yellow): Transition after Red.
q2 (Green): Go – vehicles can move.
q3 (Yellow): Prepare to stop – before Red.

Timer
start Red Yellow 1

Timer
Timer

Yellow 2 Green
Timer

7 / 184
Example-3: Elevator (Lift)
To better understand finite automata, let’s consider a
simple example involving an elevator system with four
floors: Ground, First, Second, and Third floor.

Formal Definition:
Let the finite automaton be defined as a 5-tuple:

M = (Q, Σ, δ, q0 , F)

Where:
Q = {q0 , q1 , q2 , q3 } — States: Ground, First,
Second, Third Floor
Σ = {0, 1, 2, 3} — Inputs: Floor button
selections
q0 — Initial state (Ground floor)
F = {q3 } — Final state (Third floor)
8 / 184
Elevator: Transition Table and State Diagram

Transition Function δ

δ 0 1 2 3

q0 q0 q1 q2 q3

q1 q0 q1 q2 q3

q2 q0 q1 q2 q3

q3 q0 q1 q2 q3

9 / 184
Elevator: Transition Table and State Diagram

State Diagram

3
0 2
2
1 2 3
start q0 q1 q2 q3 3
0 1 2
0 1 3
1
0

10 / 184
Features of Finite Automata

A Finite Automaton contains five tuples: {Q, Σ, q0 , F, δ}.

Q is a finite set of states.

Σ represents a finite set of input symbols (alphabet).

δ is the transition function.

q0 is the initial state, where q0 ∈ Q.

F is a set of final (accepting) states, where F ⊆ Q.

Key Components: States, Alphabet, Transition Function, Initial State, and

Final States.

11 / 184
Working of Finite Automata
Every automaton takes a language as input, processes it through its state ma-
chine, and outputs whether the input string is accepted or rejected based on its
final state.

L1 L2 ··· Ln Input

Automata Machine
{q0 , q1 , q2 , . . . , qn } States of Automata

O1 O2 ··· On Output

12 / 184
What is an Informal Finite Automaton?
An informal finite automaton is a conceptual model that explains how a
system or process moves through different stages (called states) based on
inputs or actions.

It focuses on the logical flow of events without formal mathematical

notation.

It is useful for visualizing real-world scenarios like workflows, protocols,

or simple decision systems.

Key Characteristics:

Consists of states and transitions.

Has a clear starting point and end points.

Helps in understanding process logic in a simplified way.

13 / 184
Example: Electronic Payment Protocol

We model a simple electronic transaction involving a Customer, Store, and

Bank using an informal finite automaton. The system ensures:
No double-spending.
Goods are shipped only after payment verification.

States and Descriptions:

q0 (Start) – Customer holds digital money.
q1 (Sent) – Customer sends money to the store.
q2 (Verified) – Store verifies money with the bank.
q3 (Completed) – Goods are shipped, money is redeemed.
qf (Cancelled) – Transaction is cancelled.

14 / 184
Informal Finite Automaton

q0 send q1 verify q2
start
Start Sent Verified

cancel ship
cancel cancel

qf q3
Cancelled Completed

Explanation
The process begins in q0, where the customer has the digital money.
If the customer proceeds, they send it to the store (q1), the store verifies
it (q2), and then ships the goods (q3).
At any stage before shipping, the customer can cancel the transaction,
ending in state qf. 15 / 184
Types of Finite Automata

Finite Automata are categorized into two main types:

Finite Au-
tomata

Deterministic Non deter-

Finite Au- ministic Finite
tomaton Automaton
(DFA) (NFA)

16 / 184
Deterministic Finite Automata (DFA)
A DFA is defined as a 5-tuple: {Q, Σ, δ, q0 , F}
where
Q is the set of all states.
Σ is the set of input symbols.
δ : Q × Σ → Q is the transition function.
q0 is the initial state.
F is the set of final (accept) states.

Note:
For a particular input symbol, the machine moves to only one state.
ε (null) transitions are not allowed.
It means the state cannot change without an input symbol.

17 / 184
Example 1

Construct a DFA which accept a language of all strings starting with ‘0’
over two alphabets Σ = {0, 1}

Language:
L = {0, 00, 01, 000, 001, 010, 011, . . . }
This DFA accepts all binary strings that start with the symbol ‘0’.
Transition Diagram:
0,1 0,1
Accept Reject
0 1 0
01 10 q0 q1 q∅
start
001 101
Trap State
1

18 / 184
Example 1
DFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q∅ }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q1 q∅
q1 q1 q1
q∅ q∅ q∅
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

19 / 184
Example 2

Construct a DFA which accept a language of all strings starting with ‘1’
over two alphabets Σ = {0, 1}

Language:
L = {1, 10, 11, 100, 101, 110, 111, . . . }
This DFA accepts all binary strings that start with the symbol ‘1’.
Transition Diagram:

0,1 0,1
Accept Reject
1 0
1
10 01
100 001 start q0 q1 q∅

Trap State
0

20 / 184
Example 2
DFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q∅ }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q∅ q1
q1 q1 q1
q∅ q∅ q∅
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

21 / 184
Example 3

Design a DFA over the alphabet Σ = {0, 1} that accepts all strings ending
in “01”

Language:
L = {01, 001, 101, 0001, 0101, 1101, 11001, 01101 . . . }
This DFA accepts all binary strings that end with the symbol “01”.

Transition Diagram:
Accept Reject
01 11 1 0
001 011 0
0101 1010 q0 q1 q2
start
11001 11000 0 1
01100101 10011100
1

22 / 184
Example 3
DFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q1 q0
q1 q1 q2
q2 q1 q0
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

23 / 184
Example 4
Design a DFA to accept the language L which has both an even number of
0’s and an even number of 1’s.

Language:
L = {w ∈ {0, 1}∗ | w has even number of 0s and even number of 1s}
We can define a language L as follows
L = {0011, 0110, 110110, 1001, · · · }
Transition Diagram:
0
start q0 q1
Accept Reject 0
0011 0111 1 1 1 1
0110 0001 0
110110 100110
q2 q3

0 24 / 184
Example 4
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q1 q2
q1 q0 q3
q2 q3 q0
q3 q2 q1

Initial State q0 = q0 ∈ Q

Accept State F = {q0 } ⊆ Q

25 / 184
Example 5

A vending machine in a Delhi market accepts coins of Rs. 5 and Rs. 10 .

The machine dispenses a lucky ladoo only when the total amount inserted
is exactly Rs. 15. Design a DFA that accepts strings over the alphabet
{5,10} representing coin sequences where the total value is exactly Rs. 15.

Let F is denoted as Rs. 5 and T is denoted as Rs. 10

Language:

L = {FFF, FT, TF}

Accept Reject
FT FF
TF TT
FFF FTF

26 / 184
Example 5

Transition Diagram

q0 F q1 F q2 F q3
start

T T F,T

q∅ F,T

Trap State

27 / 184
Example 5
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q3 , q∅ }

Inputs Σ = {F, T}

Transition function δ :
Input
F T
State
q0 q1 q2
q1 q2 q3
q2 q3 q∅
q3 q∅ q∅
q∅ q∅ q∅

Initial State q0 = q0 ∈ Q

Accept State F = {q3 } ⊆ Q

28 / 184
Example 6

Design a deterministic finite automaton (DFA) that accepts FASTag RFID

(Radio Frequency Identification) codes matching the pattern based on the
vehicle type code C for Car, B for Bus, or T for Truck and followed by a
single digit that between 0 to 9.

Language:

L = {x | x = vt, v ∈ {C, B, T}, t ∈ {0, 1, 2, 3, · · · , 9}

L = {{C, B, T}, {0, 1, 2, 3, · · · , 9}}

29 / 184
Example 6

Transition Diagram

C, B, T 0–9
start q0 q1 q2

C,B,T
0–9 C,B,T, 0–9

q∅ C,B,T, 0–9

Trap State

30 / 184
Example 6
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q∅ }

Inputs Σ = {{C, B, T}, 0 − 9}

Transition function δ :
Input
C,B,T 0-9
State
q0 q1 q∅
q1 q∅ q2
q2 q∅ q∅
q∅ q∅ q∅

Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

31 / 184
Example 7

Design a finite automaton that accepts passwords matching the pattern:

Starts with a capital letter (A–Z)
Followed by two digits (0–9)
Ends with a special character (@, #, $)

Language:

L = {x | x = uvw, u ∈ {A − Z}, v ∈ {0 − 9}, w ∈ {@, #, $}

L = {{A − Z}, {0 − 9}, {@, #, $}}

32 / 184
Example 7

Transition Diagram

A–Z 0–9 0–9 @, #, $

start q0 q1 q2 q3 q4

A–Z,
A–Z, @, #, $ A–Z,
@, #, $ 0–9 A–Z,
0–9,
0–9,
@, #, $ q∅ @, #, $
Trap State A–Z,
0–9,
@, #, $

33 / 184
Example 7
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q3 , q4 , q∅ }
Inputs Σ = {{A − Z}, {0 − 9}, {@, #, $}
Transition function δ :
Input
A-Z 0-9 @, #, $
State
q0 q1 q∅ q∅
q1 q∅ q2 q∅
q2 q∅ q3 q∅
q3 q∅ q∅ q4
q4 q∅ q∅ q∅
q∅ q∅ q∅ q∅

Initial State q0 = q0 ∈ Q
Accept State F = {q4 } ⊆ Q
34 / 184
Exercise Problems

1. Construct a DFA that accepts input strings of 0’s and 1’s that ends with “11”

2. Design a DFA to accept strings over Σ = {0, 1} with three consecutive 0’s.

3. Construct a DFA that accepts sets of all strings over {0,1} of length 2. [Hint:
Use trap state (dead state)]

4. Design a DFA to accept even number of a’s and b’s

5. Construct a DFA that accepts any string over {a,b} that does not contain the
string “aabb” in it.
35 / 184
Exercise Problems

6. An industrial robot operates in a factory and processes a sequence of com-

mands {m, s, h} (move = m, sense = s, halt = h). For safety, the robot must halt
after sensing an obstacle, i.e., it accepts sequences containing “sh” (sense fol-
lowed by halt). Design a DFA to ensure the robot follows this safety protocol.

7. A system monitors log files for error patterns over the alphabet e, w, n (error
= e, warning = w, normal = n). It flags logs that contain at least two consecutive
errors (“ee”) to trigger an alert. Design a DFA to detect such error patterns.

36 / 184
Exercise Problems

8. Design a DFA for an exam monitoring system that processes logs over the
alphabet {s,c,f}, where s represents a student signing in, c represents complet-
ing the exam, and f indicates a cheating flag. The system should accept only
valid session logs that begin with a sign-in (s) and do not contain any instance
of cheating (f). Any log that starts with c or includes the character f should be
rejected, transitioning to a trap state. Construct a DFA that enforces this rule.

37 / 184
Exercise 1: Construct a DFA that accepts input strings
of 0’s and 1’s that ends with “11”
Language:
L = {11, 011, 111, 0011, 0111, 1111, 00011, 00111, 01111, 01011, . . . }
This DFA accepts all binary strings that ends with “11”.

Accept Reject
11 10
011 101
1011 1001
11011 11001
Transition Diagram
0 1
0

q0 1 q1 1 q2
start

0
38 / 184
Exercise 1
DFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q0 q1
q1 q1 q2
q2 q2 q2
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

39 / 184
Exercise 2: Design a DFA to accept strings over
Σ = {0, 1} with three consecutive 0’s.
Language:
L = {000, 0001, 1000, 0000, 00011, 11000, 000011, 110000, 000111, . . . }
Accept Reject
000 001
0001 0010
1000 1001
01000 10100
0010001 001001
Transition Diagram
1 0,1
1

q0 0 q1 0 q2 0 q3
start

1 40 / 184
Exercise 2
DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q1 q0
q1 q2 q1
q2 q3 q2
q3 q3 q3
Initial State q0 = q0 ∈ Q

Accept State F = {q3 } ⊆ Q

41 / 184
Exercise 3

Construct a DFA that accepts sets of all strings over {0,1} of length 2.
[Hint: Use trap state (dead state)].

Language:
L = {00, 01, 10, 11}
This DFA accepts all binary strings that of length 2.

Transition Diagram

0,1

0,1 0,1 0,1

start q0 q1 q2 q∅

Trap State

42 / 184
Exercise 3
DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q∅ }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 q1 q1
q1 q2 q2
q2 q∅ q∅
q∅ q∅ q∅
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

43 / 184
Exercise 4
Design a DFA to accept even number of a’s and b’s.

Language:
L = {w ∈ {0, 1}∗ | w has even number of a’s and even number of b’s}
We can define a language L as follows
L = {aabb, abba, bbabba, baab, · · · }
Transition Diagram:
a

Accept Reject start q0 q1

aabb abbb a
abba aaab b b b b
abbabb bababa a
bbabba aaabbb
q2 q3
a
44 / 184
Exercise 4
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 q1 q2
q1 q0 q3
q2 q3 q0
q3 q2 q1

Initial State q0 = q0 ∈ Q

Accept State F = {q0 } ⊆ Q

45 / 184
Exercise 5

Construct a DFA that accepts any string over {a,b} that does not contain
the string “aabb” in it.

Let us consider a language which contains the string “aabb” in it.

Language:
L = {aabb, aaabb, baabb, aaabba, aaabbb, babaaabb, . . . }
This DFA accepts all strings that contains the string “aabb”.

Accept Reject
aabb abab
baabb babaa
baaabb aaabaa
abaabb baaaba
abaabba aabaaab
baabaabb ababaaab

46 / 184
Exercise 5

Transition Diagram

b a a,b

q0 a q1 a q2 b q3 b q4
start
b
a

47 / 184
Exercise 5
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q3 , q4 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 q1 q0
q1 q2 q0
q2 q2 q3
q3 q1 q4
q4 q4 q4
Initial State q0 = q0 ∈ Q

Accept State F = {q4 } ⊆ Q

48 / 184
Exercise 5

The above DFA accepts any string over {a, b} that contains the substring
“aabb”.

Note:
We need a DFA that accepts any string over {a, b} that does not contain
the substring “aabb”.

It is easy to obtain such a DFA by making the following changes:

Final State =⇒ Non Final State.

Non Final State =⇒ Final State.

49 / 184
Exercise 5

Construct a language consisting of all strings over {a,b} that do not contain the
substring “aabb”.

Language:
L = {abab, abba, aaaba, babaaab, . . . }
This DFA accepts all strings that does not contains the string “aabb”.

Transition Diagram

b a a,b

q0 a q1 a q2 b q3 b q4
start
b
a

50 / 184
Exercise 5
DFA:
M = {Q, Σ, δ, q0 , F}
States Q = {q0 , q1 , q2 , q3 , q4 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 q1 q0
q1 q2 q0
q2 q2 q3
q3 q1 q4
q4 q4 q4
Initial State q0 = q0 ∈ Q

Accept State F = {q0 , q1 , q2 , q3 } ⊆ Q

51 / 184
Exercise 6

An industrial robot operates in a factory and processes a sequence of com-

mands {m, s, h} (move = m, sense = s, halt = h). For safety, the robot must
halt after sensing an obstacle, i.e., it accepts sequences containing “sh”
(sense followed by halt). Design a DFA to ensure the robot follows this
safety protocol.

Language:
L = {sh, msh, ssshmhmsh, mmsmsh, smhsh, . . . }

Accept Reject
sh ss
msh mhs
smhsh ssmhs

52 / 184
Exercise 6

Transition Diagram

m, h s m, s, h
s
q0 q1 h q2
start
m

53 / 184
Exercise 6

DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {m, s, h}

Transition function δ :
Input
m s h
State
q0 q0 q1 q0
q1 q0 q1 q2
q2 q2 q2 q2
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

54 / 184
Exercise 7

A system monitors log files for error patterns over the alphabet e, w, n
(error = e, warning = w, normal = n). It flags logs that contain at least two
consecutive errors (“ee”) to trigger an alert. Design a DFA to detect such
error patterns.

Language:
L = {ee, nee, weee, neewn, eenen, . . . }

Accept Reject
ee en
nee ene
weee wene

55 / 184
Exercise 7

Transition Diagram

w, n e, w, n
e
q0 q1 e q2
start
w, n

56 / 184
Exercise 7

DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {e, w, n}

Transition function δ :
Input
e w n
State
q0 q1 q0 q0
q1 q2 q0 q0
q2 q2 q2 q2
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

57 / 184
Exercise 8

Design a DFA for an exam monitoring system that processes logs over the
alphabet {s,c,f}, where s represents a student signing in, c represents com-
pleting the exam, and f indicates a cheating flag. The system should accept
only valid session logs that begin with a sign-in (s) and do not contain any
instance of cheating (f). Any log that starts with c or includes the char-
acter f should be rejected, transitioning to a trap state. Construct a DFA
that enforces this rule.

Language:
L = {s, ss, sc, sss, ssc, . . . }

Accept Reject
s f
ss cs
ssc ssf

58 / 184
Exercise 8

Transition Diagram
s, c
s
start q0 q1

f
c, f
q∅ s, c, f

Trap State

59 / 184
Exercise 8

DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q∅ }

Inputs Σ = {s, c, f }

Transition function δ :
Input
s c f
State
q0 q1 q∅ q0
q1 q2 q0 q0
q2 q2 q2 q2
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

60 / 184
Extended Transition Function in DFA

The extended transition function δ̂ is defined as

δ̂(q, ϵ) = q
 
δ̂(q, w) = δ δ̂(q, x), a for x ∈ Σ∗ , a ∈ Σ

Note:
Here w = xa is a string; that is, a is the last symbol of w, and x is the string
consisting of all but not the last symbol.

Let w = 1101 be a string and we can broaken into x = 110 and a = 1

61 / 184
Example of Extended Transition Function

Process the string 101 for the transition diagram given below

0 0
1

start q0 q1

States: Q = {q0 , q1 }

Alphabet: Σ = {0, 1}

Start state: q0

62 / 184
Example of Extended Transition Function

Transition function:

δ(q0 , 0) = q0

δ(q0 , 1) = q1

δ(q1 , 0) = q1

δ(q1 , 1) = q0

Transition table:
Input
0 1
State
q0 q0 q1
q1 q1 q0

63 / 184
Computation of δ̂(q0 , 101)

δ̂(q0 , ∅) = q0
 
δ̂(q0 , 1) = δ δ̂(q0 , ∅), 1 = δ(q0 , 1) = q1
 
δ̂(q0 , 10) = δ δ̂(q0 , 1), 0 = δ(q1 , 0) = q1
 
δ̂(q0 , 101) = δ δ̂(q0 , 10), 1 = δ(q1 , 1) = q0

Result: The DFA ends in state q0 after reading input string “101”.

64 / 184
Language of a DFA

We can define the language of a DFA

M = (Q, Σ, δ, q0 , F)

This language is denoted as L(M), and is defined by

L(A) = {w | δ̂(q0 , w) ∈ F}

That is, the language of M is the set of strings w that take the start state
qo to one of the accepting states.

If L is L(M) for some DFA M, then we say L is regular language.

65 / 184
Nondeterministic Finite Automata
An Nondeterministic Finite Automata (NFA) is a 5-tuple:

M = (Q, Σ, δ, q0 , F)
where,
Q is a finite set of states.
Σ is a finite set of input symbols.
δ : Q × Σ → 2Q is a transition function.
q0 ∈ Q is the start state.
F ⊆ Q is the set of accepting/final state.
Note:
For a particular input symbol, the machine can moves to multiple
states.
If Q = {q0 , q1 }, then 2Q = {∅, {q0 }, {q1 }, {q0 , q1 }}
66 / 184
Concept of NFA Construction
Start with “101”:
0,1

q0 1 q1 0 q2 1 q3
start

Containing “101”:
0,1 0,1

q0 1 q1 0 q2 1 q3
start

End with “101”:

0,1

q0 1 q1 0 q2 1 q3
start

67 / 184
Example 1
Construct an NFA accepting the strings over Σ = {0, 1} that end with “0”.

Language:
L = {0, 00, 10, 000, 010, 100, . . . }
This NFA accepts all strings that ends with “0”.

Accept Reject
0 1
10 01
001010 100101
Transition Diagram
0,1

q0 0 q1
start

68 / 184
Example 1

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 {q0 , q1 } {q0 }
q1 − −
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

69 / 184
Example 2
Construct an NFA accepting the strings over Σ = {a, b} ending in “aba”.

Language:
L = {aba, aaba, aaaba, baba, bbaba, ababa, . . . }
This NFA accepts all strings that ends with “aba”.

Accept Reject
aba bba
aaba aaaa
abaaba abbaab
Transition Diagram
a,b

q0 a q1 b q2 a q3
start

70 / 184
Example 2
NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 {q0 , q1 } {q0 }
q1 − {q2 }
q2 {q3 } −
q3 − −
Initial State q0 = q0 ∈ Q

Accept State F = {q3 } ⊆ Q

71 / 184
Example 3
Construct an NFA accepting the language L over Σ = {a, b} which has
length of the string atleast 3 and the third symbol of the string from the
right side is ‘b’.

Language:
L = {baa, bbb, bab, bba, aaabaa, bbbaabbb, . . . }
Accept Reject
baa abb
aaabaa abaaba
ababab abbaab
Transition Diagram
a,b

b a,b a,b
start q0 q1 q2 q3

72 / 184
Example 3
NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 {q0 } {q0 , q1 }
q1 {q2 } {q2 }
q2 {q3 } {q3 }
q3 − −
Initial State q0 = q0 ∈ Q

Accept State F = {q3 } ⊆ Q

73 / 184
Example 4
Construct an NFA accepting the strings over Σ = {0, 1} ending in “01”.

Language:
L = {01, 001, 0101, 001101, . . . }
This NFA accepts all strings that ends with “01”.

Accept Reject
01 10
001 111
0101101 0101110
Transition Diagram
0,1

q0 0 q1 1 q2
start

74 / 184
Example 4

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 {q0 , q1 } {q0 }
q1 − {q2 }
q2 − −
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

75 / 184
Example 5
Construct a nondeterministic finite automaton (NFA) over the alphabet
Σ = {a, b} that accepts all strings which contain the substring “ab” at
least once.

Language:
L = { ab, aab, bab, cab, babab, abb, . . . }

Accept Reject
ab aa
abaab baaaa
ababaa bbbbba
Transition Diagram:
a, b a, b

a b
start q0 q1 q2

76 / 184
Example 5
NFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 {q0 , q1 } {q0 }
q1 – {q2 }
q2 {q2 } {q2 }
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

77 / 184
Example 6

Construct an NFA over the alphabet Σ = {a, b} that accepts the language
L = {(ab)n | n ≥ 1}

Language:

Let n = 1 =⇒ (ab)n = (ab)1 = ab

Let n = 2 =⇒ (ab)n = (ab)2 = abab

Let n = 3 =⇒ (ab)n = (ab)3 = ababab

Let n = 4 =⇒ (ab)n = (ab)4 = abababab

..
.

L = {ab, abab, ababab, abababab, . . .}

78 / 184
Example 6

Accept Reject
ab ba
abab abba
ababab ababa

Transition Diagram:

a b
start q0 q1 q2

79 / 184
Example 6
NFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 {q1 } −
q1 – {q2 }
q2 {q1 } –
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

80 / 184
Example 7

Construct an NFA over the alphabet Σ = {0, 1} that accepts the language
L = {0m 1n | m ≥ 0 and n ≥ 1}

Language:

Let m = 0, n = 1 =⇒ 0m 1n = 00 11 = 1

Let m = 1, n = 2 =⇒ 0m 1n = 01 12 = 011

Let m = 2, n = 3 =⇒ 0m 1n = 02 13 = 00111

Let m = 3, n = 4 =⇒ 0m 1n = 03 14 = 0001111
..
.

L = {1, 011, 00111, 0001111, . . .}

81 / 184
Example 7

Accept Reject
1 0
011 110
00111 11100

Transition Diagram:

0 1

1
start q0 q1

82 / 184
Example 7

NFA:

M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 {q0 } {q1 }
q1 – {q1 }
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

83 / 184
Example 8

A file scanner monitors filename extensions to detect whether a given input

string could represent the start of a valid file format such as .pdf, .doc. The
file name consists of lowercase letters (a–z), followed by a dot (.), and then
a known extension. If any of these known extensions are found, the system
flags the file. Use an NFA to detect such patterns.

Language:

L = {{a − z}, ·, p, d, f , o, c}

84 / 184
Example 8

Transition Diagram
a–z

· p d f
start q0 q1 q2 q3 q4

q5 o q6 c q7

85 / 184
Example 8

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q3 , q4 , q5 , q6 , q7 }

Inputs Σ = {{a − z}, ·, p, d, f , o, c}

Initial State q0 = q0 ∈ Q

Accept State F = {q4 , q7 } ⊆ Q

86 / 184
Example 8

Transition function δ :

Input
a−z · p d f o c
State
q0 {q0 } {q1 } − − − − −
q1 − − {q2 } {q5 } − − −
q2 − − − {q3 } − − −
q3 − − − − {q4 } − −
q4 − − − − − − −
q5 − − − − − {q6 } −
q6 − − − − − − {q7 }
q7 − − − − − − −

87 / 184
Example 9

Design a finite automaton (NFA) that accepts passwords matching the pattern:
Starts with a capital letter (A–Z)
Followed by two digits (0–9)
Ends with a special character (@, #, $)

Language:

L = {x | x = uvw, u ∈ {A–Z}, v ∈ {0–9}2 , w ∈ {@, #, $}}

88 / 184
Example 9

Transition Diagram

A–Z 0–9 0–9 @, #, $

start q0 q1 q2 q3 q4

89 / 184
Example 9

NFA:
M = {Q, Σ, δ, q0 , F}

States: Q = {q0 , q1 , q2 , q3 , q4 }
Input symbols: Σ = {A–Z, 0–9, @, #, $}
Transition function δ is defined by the table below:
Input
A–Z 0–9 @, #, $
State
q0 {q1 } ∅ ∅
q1 ∅ {q2 } ∅
q2 ∅ {q3 } ∅
q3 ∅ ∅ {q4 }
q4 ∅ ∅ ∅
Start state: q0
Accepting state: F = {q4 }

90 / 184
Exercise

1. Construct an NFA accepting the strings over Σ = {0, 1} that end with “1”.

2. Construct an NFA accepting the strings over Σ = {a, b} ending in “aaa”.

3. Construct an NFA accepting the strings over Σ = {a, b} that start with “a”.

4. Construct an NFA that accepts sets of all strings over {0,1} of length 2.

5. A website allows usernames that consist of lowercase letters {a − z} and

must contain at least one digit (0–9) somewhere in the string. Design a non-
deterministic finite automaton (NFA) that accepts such usernames. The NFA
should accept strings like abc3def, 1user, or xyz9, but reject strings like user,
hello, or abcxyz.

91 / 184
Exercise 1
Construct an NFA accepting the strings over Σ = {a, b} that end with “1”.

Language:
L = {1, 01, 11, 001, 011, 101, 111 . . . }
This NFA accepts all strings that ends with “1”.

Accept Reject
1 0
01 00
001011 100100
Transition Diagram
0,1

q0 1 q1
start

92 / 184
Exercise 1

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 {q0 , q1 } {q0 }
q1 − {q1 }
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

93 / 184
Exercise 2
Construct an NFA accepting the strings over Σ = {a, b} ending in “aaa”.

Language:
L = {aaa, aaaa, baaa, abaaa, bbaaa, abaaaa, . . . }
This NFA accepts all strings that ends with “aaa”.

Accept Reject
aaa aba
aaaa aaba
abaaaa ababaa
Transition Diagram
a,b

q0 a q1 a q2 a q3
start

94 / 184
Exercise 2
NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b
State
q0 {q0 , q1 } {q0 }
q1 {q2 } −
q2 {q3 } −
q3 − −
Initial State q0 = q0 ∈ Q

Accept State F = {q3 } ⊆ Q

95 / 184
Exercise 3
Construct an NFA accepting the strings over Σ = {a, b} that start with
“a”.

Language:
L = {a, aa, ab, aaa, aba, abb, . . . }
This NFA accepts all strings that starts with “a”.

Accept Reject
a b
ab ba
abbaa bbbaa
Transition Diagram
a,b

q0 a q1
start

96 / 184
Exercise 3

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 }

Inputs Σ = {a, b}

Transition function δ :
Input
0 1
State
q0 {q1 } −
q1 {q1 } {q2 }
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

97 / 184
Exercise 4

Construct an NFA that accepts sets of all strings over {0,1} of length 2.

Language:
L = {00, 01, 10, 11}
This NFA accepts all binary strings that of length 2.

Transition Diagram

0,1 0,1
start q0 q1 q2

98 / 184
Exercise 4

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {0, 1}

Transition function δ :
Input
0 1
State
q0 {q1 } {q1 }
q1 {q2 } {q2 }
q2 − −
Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

99 / 184
Exercise 5

A website allows usernames that consist of lowercase letters {a − z} and

must contain at least one digit (0–9) somewhere in the string. Design a non-
deterministic finite automaton (NFA) that accepts such usernames. The
NFA should accept strings like abc3def, 1user, or xyz9, but reject strings
like user, hello, or abcxyz.

Language:

L = {{a − z}, {0 − 9}}

Accept Reject
1user user
xyz9 XYZ
hello123hello hello

100 / 184
Exercise 5

Transition Diagram

a-z a-z, 0-9

0-9
start q0 q1

101 / 184
Exercise 5

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 }

Inputs Σ = {{a − z}, {0 − 9}}

Transition function δ :
Input
a−z 0−9
State
q0 {q0 } {q1 }
q1 {q1 } {q1 }
Initial State q0 = q0 ∈ Q

Accept State F = {q1 } ⊆ Q

102 / 184
DFA vs NFA

DFA NFA
It allows only one move for It allows more than one move
single input symbol. for single input symbol.
It cannot use empty string It can use empty string
transition. transition.
Dead (Trape) State may be Dead (Trape) state is not
required. required.
It requires more space. It requires less space.
It is difficult to construct. It is easy to construct.
All DFA’s are NFA. Not all NFA’s are DFA.
Both DFA and NFA can have multiple final states.

103 / 184
Extended Transition Function in NFA

The extended transition function δ̂ is defined as

δ̂(q, ϵ) = {q}

Suppose w is of the form w = xa, where a is the last symbol of w and x is

the rest of w.

Also suppose that δ̂(q, x) = {p1 , p2 , . . . , pk }.

Let
k
[
δ(pi , a) = {r1 , r2 , . . . , rm }
i=1

Then δ̂(q, w) = {r1 , r2 , . . . , rm }

104 / 184
Example of Extended Transition Function

Process the string 00101 for the NFA transition diagram given below

0,1

q0 0 q1 1 q2
start

States: Q = {q0 , q1 , q2 }

Alphabet: Σ = {0, 1}

Start state: q0

105 / 184
Example of Extended Transition Function

Transition function:

δ(q0 , 0) = {q0 , q1 }
δ(q0 , 1) = {q0 }
δ(q1 , 0) = ∅
δ(q1 , 1) = {q2 }
δ(q2 , 0) = ∅
δ(q2 , 1) = ∅

Transition table:
Input
0 1
State
q0 {q0 , q1 } {q0 }
q1 − {q2 }
q2 − −

106 / 184
Computation of δ̂(q0 , 00101)

δ̂(q0 , ϵ) = {q0 }
δ̂(q0 , 0) = δ(q0 , 0) = {q0 , q1 }
δ̂(q0 , 00) = δ(q0 , 0) ∪ δ(q1 , 0) = {q0 , q1 } ∪ ∅ = {q0 , q1 }
δ̂(q0 , 001) = δ(q0 , 1) ∪ δ(q1 , 1) = {q0 } ∪ {q1 } = {q0 , q2 }
δ̂(q0 , 0010) = δ(q0 , 0) ∪ δ(q2 , 0) = {q0 , q1 } ∪ ∅ = {q0 , q1 }
δ̂(q0 , 00101) = δ(q0 , 1) ∪ δ(q1 , 1) = {q0 } ∪ {q1 } = {q0 , q2 }

Result: The NFA ends in state {q0 , q2 } after reading input string “00101”.

107 / 184
Language of an NFA

We can define the language of an NFA

M = (Q, Σ, δ, q0 , F)

This language is denoted as L(M), and is defined by

L(A) = {w | δ̂(q0 , w) ∩ F ̸= ∅}

That is, the language of M is the set of strings w in Σ∗ such that δ̂(q0 , w)
contains at least one accepting state.

108 / 184
Conversion of NFA to DFA

Theorem: For every NFA, there exists a DFA that accepts the same language.
That is,
L(N) = L(D).

Given a N = (Q̄, Σ, α, q0 , F̄),

we construct a D = (Q, Σ, δ, q0 , F)
where,
Q = 2Q̄ (i.e., the power set of Q̄)
For each subset S ⊆ Q̄ and each input a ∈ Σ,
[
δ(S, a) = α(q, a)
q∈S

F = {S ⊆ Q̄ | S ∩ F̄ ̸= ∅}

109 / 184
Example 1
Convert to a DFA the following NFA.
Let N = ({q0 , q1 }, {0, 1}, δN , q0 , {q1 })
where δN is given by

δN (q0 , 0) = {q0 , q1 }
δN (q0 , 1) = {q1 }
δN (q1 , 0) = ∅
δN (q1 , 1) = {q0 , q1 }

Solution:
Given NFA
States QN = {q0 , q1 } =⇒ |QN | = 2
Input Σ = {0, 1}
Start state q0N = q0
Final state FN = {q1 }
110 / 184
Example 1

Transition Table:
α 0 1
q0 {q0 , q1 } {q1 }
q1 − {q0 , q1 }

Transition Diagram:

0 1
0,1

start q0 q1

111 / 184
Example 1

Construct a DFA

D = (QD , {0, 1}, δD , q0D , FD )

Find the subsets

QD = 2|QN |
QD = 22 = 4
QD = {∅, {q0 }, {q1 }, {q0 , q1 }}

112 / 184
Example 1

Transition Table of DFA:

Find the transition function for the subsets QD whichever is required.

δ 0 1
q0 {q0 , q1 } {q1 }
q1 α(q1 , 0) = ∅ α(q1 , 1) = {q0 , q1 }
α(q0 , 0) ∪ α(q1 , 0) α(q0 , 1) ∪ α(q1 , 1)
q0 , q1 = {q0 , q1 } ∪ ∅ = {q1 } ∪ {q0 , q1 }
= {q0 , q1 } = {q0 , q1 }
q∅ q∅ q∅

113 / 184
Example 1

Transition Diagram:

0,1
0

q0 1 q1 1 q0 , q1
start

q∅ 0,1

Trap State

114 / 184
Example 1

The constructed DFA is

D = (QD , Σ, δD , q0D , FD )
where,
QD = {q0 , q1 , (q0 , q1 ), q∅ }
Σ = {0, 1}
q0D = q0
FD = {q1 , (q0 , q1 )} ⊆ QD

115 / 184
Example 2
Design a DFA from the given NFA
0 1

q0 0 q1
start

0 1
q2

Solution:
Given NFA
States QN = {q0 , q1 , q2 } =⇒ |QN | = 3
Input Σ = {0, 1}
Start state q0N = q0
Final state FN = {q0 }
116 / 184
Example 2

Transition Table:
α 0 1
q0 {q0 , q1 } ∅
q1 ∅ {q1 , q2 }
q2 q0 ∅

117 / 184
Example 1

Construct a DFA

D = (QD , {0, 1}, δD , q0D , FD )

Find the subsets

QD = 2|QN |
QD = 23 = 8
QD = {∅, {q0 }, {q1 }, {q2 }, {q0 , q1 }, {q0 , q2 }, {q1 , q2 }, {q0 , q1 , q2 }}

118 / 184
Example 2

Transition Table of DFA:

Find the transition function for the subsets QD whichever is required.

δ 0 1
{q0 } {q0 , q1 } q∅
α(q0 , 0) ∪ α(q1 , 0) α(q0 , 1) ∪ α(q1 , 1)
{q0 , q1 } = {q0 , q1 } ∪ ∅ = ∅ ∪ {q1 , q2 }
= {q0 , q1 } = {q1 , q2 }
α(q1 , 0) ∪ α(q2 , 0) α(q1 , 1) ∪ α(q2 , 1)
{q1 , q2 } = ∅ ∪ {q0 } = {q1 , q2 } ∪ ∅
= {q0 } = {q1 , q2 }
q∅ q∅ q∅

119 / 184
Example 2

Transition Diagram:

q0 0 q0 , q1
start

1 1
0

0,1 q∅ q1 , q2 1
Trap State

120 / 184
Example 2

The constructed DFA is

D = (QD , Σ, δD , q0D , FD )
where,
QD = {q0 , (q0 , q1 ), (q1 , q2 ), q∅ }
Σ = {0, 1}
q0D = q0
FD = {q0 , (q0 , q1 )} ⊆ QD

121 / 184
Exercise Problem

1. Design an equivalent DFA for the following NFA.

Let N = ({q0 , q1 }, {0, 1}, δN , q0 , {q1 })
where δN is given by

δN (q0 , 0) = {q0 , q1 }
δN (q0 , 1) = {q1 }
δN (q1 , 0) = {q1 }
δN (q1 , 1) = {q0 }

122 / 184
Exercise 1
Design an equivalent DFA for the following NFA.
Let N = ({q0 , q1 }, {0, 1}, δN , q0 , {q0 })
where δN is given by

δN (q0 , 0) = {q0 , q1 }
δN (q0 , 1) = {q1 }
δN (q1 , 0) = {q1 }
δN (q1 , 1) = {q0 }

Solution:
Given NFA
States QN = {q0 , q1 } =⇒ |QN | = 2
Input Σ = {0, 1}
Start state q0N = q0
Final state FN = {q0 }
123 / 184
Exercise 1

Transition Table:
α 0 1
q0 {q0 , q1 } {q1 }
q1 {q1 } {q0 }

Transition Diagram:

0 0
0,1

start q0 q1

124 / 184
Exercise 1

Construct a DFA

D = (QD , {0, 1}, δD , q0D , FD )

Find the subsets

QD = 2|QN |
QD = 22 = 4
QD = {∅, {q0 }, {q1 }, {q0 , q1 }}

125 / 184
Exercise 1

Transition Table:

Find the transition function for the subsets QD whichever is required.

δ 0 1
q0 {q0 , q1 } {q1 }
q1 {q1 } {q0 }
α(q0 , 0) ∪ α(q1 , 0) α(q0 , 1) ∪ α(q1 , 1)
q0 , q1 = {q0 , q1 } ∪ {q1 } = {q1 } ∪ {q0 }
= {q0 , q1 } = {q0 , q1 }

126 / 184
Exercise 1

Transition Diagram:

start q0 q1 0

q0 , q1 0,1

127 / 184
Exercise 1

The constructed DFA is

D = (QD , Σ, δD , q0D , FD )
where,
QD = {q0 , q1 , (q0 , q1 )}
Σ = {0, 1}
q0D = q0
FD = {q0 , (q0 , q1 )} ⊆ QD

128 / 184
ε − NFA
An ε − NFA is a 5-tuple:

M = (Q, Σ, δ, q0 , F)
where,
Q is a finite set of states.
Σ is a finite set of input symbols.
δ : Q × (Σ ∪ ε) → 2Q is a transition function.
q0 ∈ Q is the start state.
F ⊆ Q is the set of accepting/final state.
Note:
The machine can transition to multiple states on a single input symbol
or ε.
An ε-transition allows the automaton to change states without
consuming any input symbol. 129 / 184
Example 1
Construct an ε-NFA accepting all strings over Σ = {a, b} that contain the
substring “ab”.

Language:
L = { ab, aab, bab, abab, abbb, aaab, baaab, . . . }
This ε-NFA accepts all strings that contain the substring “ab”.
Accept Reject
ab a
aab bb
baab bba
ababbba bbbaaaa
Transition Diagram
a,b a,b

start q0 ε q1 a q2 b q3
130 / 184
Example 1
ε-NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 , q3 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b ε
State
q0 {q0 } {q0 } {q1 }
q1 {q2 } ∅ ∅
q2 ∅ {q3 } ∅
q3 {q3 } {q3 } ∅
Initial State q0 ∈ Q

Accept State F = {q3 } ⊆ Q

131 / 184
Example 2
Construct an ε-NFA accepting all strings over Σ = {a, b} that end with
“a”.

Language:
L = { a, ba, bba, aa, baa, abba, . . . }
This ε-NFA accepts all strings that end with “a”.

Accept Reject
a b
ba bb
bba ab
Transition Diagram
a,b

start q0 ε q1 a q2

132 / 184
Example 2

ε-NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {a, b}

Transition function δ :
Input
a b ε
State
q0 {q0 } {q0 } {q1 }
q1 {q2 } ∅ ∅
q2 ∅ ∅ ∅
Initial State q0 ∈ Q

Accept State F = {q2 } ⊆ Q

133 / 184
ε - Closure

Let M = (Q, Σ, δ, q0 , F) be an ε-NFA. Then for a state q ∈ Q, the ε-closure of

q, denoted εc (q), is defined as:

εc (q) = {p ∈ Q | there is a path from q to p labeled only with ε}

Algorithm:
1 Initialize: εc (q) = {q}
2 For each p ∈ εc (q), if there is a transition δ(p, ε) = r, then add r to the
closure.

3 Repeat until no more new states are added.

134 / 184
Example: NFA with ε-Transitions

q0 ε q1 ε q2
start

135 / 184
ε-Closure of q0

Step 1: Start with q0

Step 2: q0 →
ε
− q1  add q 1

Step 3: q1 →
ε
− q2  add q 2

Result: εc (q0 ) = { q0 , q1 , q2 }

136 / 184
ε-Closure of q1

Step 1: Start with q1

Step 2: q1 →
ε
− q2  add q 2

Result: εc (q1 ) = { q1 , q2 }

137 / 184
ε-Closure of q2

Step 1: Start with q2

Step 2: No outgoing ε-transitions from q2

Result: εc (q2 ) = { q2 }

138 / 184
Summary Table of ε-Closures

State εc
q0 { q0 , q1 , q2 }
q1 { q1 , q2 }
q2 { q2 }

139 / 184
ε - NFA to NFA conversion: Example 1
Construct the following ε - NFA and find it’s equivalent NFA.

0 1 2

start q0 ε q1 ε q2

Solution:

M ={Q, Σ, δ, q0 , F}
Q ={q0 , q1 , q2 }
Σ ={0, 1, 2, ε}
q0 ={q0 } ∈ Q
F ={q2 } ⊆ Q

140 / 184
ε - NFA to NFA conversion: Example 1

Transition Table
δ 0 1 2 ε
q0 {q0 } − − {q1 }
q1 − {q1 } − {q2 }
q2 − − {q2 } −

Find the ε - closure for q0 , q1 , q2

εc (q0 ) ={q0 , q1 , q2 }
εc (q1 ) ={q1 , q2 }
εc (q2 ) ={q2 }

141 / 184
ε - NFA to NFA conversion: Example 1

Extended transition function

δ̂(q0 , 0) = εc [δ(q0 , 0) ∪ δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [{q0 } ∪ ∅ ∪ ∅]
= εc [{q0 }]
δ̂(q0 , 0) = {q0 , q1 , q2 }

δ̂(q0 , 1) = εc [δ(q0 , 1) ∪ δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [∅ ∪ {q1 } ∪ ∅]
= εc [{q1 }]
δ̂(q0 , 1) = {q1 , q2 }

142 / 184
ε - NFA to NFA conversion: Example 1

δ̂(q0 , 2) = εc [δ(q0 , 2) ∪ δ(q1 , 2) ∪ δ(q2 , 2)]

= εc [∅ ∪ ∅ ∪ {q2 }]
= εc [{q2 }]
δ̂(q0 , 2) = {q2 }

δ̂(q1 , 0) = εc [δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [∅ ∪ ∅]
= εc [∅]
δ̂(q1 , 0) = ∅

143 / 184
ε - NFA to NFA conversion: Example 1

δ̂(q1 , 1) = εc [δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [{q1 } ∪ ∅]
= εc [{q1 }]
δ̂(q1 , 1) = {q1 , q2 }

δ̂(q1 , 2) = εc [δ(q1 , 2) ∪ δ(q2 , 2)]

= εc [∅ ∪ {q2 }]
= εc [{q2 }]
δ̂(q1 , 2) = {q2 }

144 / 184
ε - NFA to NFA conversion: Example 1

δ̂(q2 , 0) = εc [δ(q2 , 0)]

= εc [∅]
δ̂(q2 , 0) = ∅

δ̂(q2 , 1) = εc [δ(q2 , 1)]

= εc [∅]
δ̂(q2 , 1) = ∅

δ̂(q2 , 2) = εc [δ(q2 , 2)]

= εc [{q2 }]
δ̂(q2 , 2) = {q2 }

145 / 184
ε - NFA to NFA conversion: Example 1

Transition table for NFA

δ̂ 0 1 2
q0 {q0 , q1 , q2 } {q1 , q2 } {q2 }
q1 ∅ {q1 , q2 } {q2 }
q2 ∅ ∅ {q2 }

146 / 184
ε - NFA to NFA conversion: Example 1

Transition diagram for NFA

0 1 2

0,1 1,2
start q0 q1 q2

0,1,2

147 / 184
ε - NFA to NFA conversion: Example 1

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {0, 1, 2}

Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

148 / 184
ε - NFA to DFA conversion: Example 1
Construct the following ε - NFA and find it’s equivalent DFA.

0 1 2

start q0 ε q1 ε q2

Solution:

M ={Q, Σ, δ, q0 , F}
Q ={q0 , q1 , q2 }
Σ ={0, 1, 2, ε}
q0 ={q0 } ∈ Q
F ={q2 } ⊆ Q

149 / 184
ε - NFA to DFA conversion: Example 1

Transition Table
δ 0 1 2 ε
q0 {q0 } − − {q1 }
q1 − {q1 } − {q2 }
q2 − − {q2 } −

Find the ε - closure for q0 , q1 , q2

εc (q0 ) ={q0 , q1 , q2 } =⇒ Let it be the state A

εc (q1 ) ={q1 , q2 } =⇒ Let it be the state B
εc (q2 ) ={q2 } =⇒ Let it be the state C

150 / 184
ε - NFA to DFA conversion: Example 1

Processing States

Process the state A:

δ ′ (A, 0) = εc [δ(q0 , 0) ∪ δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [{q0 } ∪ ∅ ∪ ∅]
= εc [{q0 }])
δ ′ (A, 0) = {q0 , q1 , q2 } = A

δ ′ (A, 1) = εc [δ(q0 , 1) ∪ δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [∅ ∪ {q1 } ∪ ∅]
= εc [{q1 }]
δ ′ (A, 1) = {q1 , q2 } = B

151 / 184
ε - NFA to DFA conversion: Example 1

δ ′ (A, 2) = εc [δ(q0 , 2) ∪ δ(q1 , 2) ∪ δ(q2 , 2)]

= εc [∅ ∪ ∅ ∪ {q2 }]
= εc [{q2 }]
′
δ (A, 2) = {q2 } = C

Process the state B:

δ ′ (B, 0) = εc [δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [∅ ∪ ∅]
= εc [∅]
δ ′ (B, 0) = ∅

152 / 184
ε - NFA to DFA conversion: Example 1

δ ′ (B, 1) = εc [δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [{q1 } ∪ ∅]
= εc [{q1 }]
′
δ (B, 1) = {q1 , q2 } = B

δ ′ (B, 2) = εc [δ(q1 , 2) ∪ δ(q2 , 2)]

= εc [∅ ∪ {q2 }]
= εc [{q2 }]
δ ′ (B, 2) = {q2 } = C

153 / 184
ε - NFA to DFA conversion: Example 1
Process the state C:

δ ′ (C, 0) = εc [δ(q2 , 0)]

= εc [∅]
δ ′ (C, 0) = ∅

δ ′ (C, 1) = εc [δ(q2 , 1)]

= εc [∅]
δ ′ (C, 1) = ∅

δ ′ (C, 2) = εc [δ(q2 , 2)]

= εc [{q2 }]
δ ′ (C, 2) = {q2 } = C

154 / 184
ε - NFA to DFA conversion: Example 1

Transition table for DFA

δ′ 0 1 2
A = {q0 , q1 , q2 } A = {q0 , q1 , q2 } B = {q1 , q2 } C = {q2 }
B = {q1 , q2 } q∅ B = {q1 , q2 } C = {q2 }
C = {q2 } q∅ q∅ C = {q2 }
q∅ q∅ q∅ q∅

155 / 184
ε - NFA to DFA conversion: Example 1

Transition diagram for DFA

0 1
1

start A B

2 0
2

2 C q∅ 0,1,2
0,1
Trap State

156 / 184
ε - NFA to DFA conversion: Example 1

DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {[q0 , q1 , q2 ], [q1 , q2 ], [q2 ]}

Inputs Σ = {0, 1, 2}

Initial State q0 = [q0 , q1 , q2 ] ∈ Q

Accept State F = {[q0 , q1 , q2 ], [q1 , q2 ], [q2 ]} ⊆ Q

157 / 184
Exercise Problems
1. Construct the following ε - NFA and find it’s equivalent NFA.

0 1 0,1

start q0 ε q1 ε q2

2. Construct the following ε - NFA and find it’s equivalent DFA.

0 1 0,1

start q0 ε q1 ε q2

158 / 184
Exercise 1
Construct the following ε - NFA and find it’s equivalent NFA.

0 1 0,1

start q0 ε q1 ε q2

Solution:

M ={Q, Σ, δ, q0 , F}
Q ={q0 , q1 , q2 }
Σ ={0, 1, ε}
q0 ={q0 } ∈ Q
F ={q2 } ⊆ Q

159 / 184
Exercise 1

Transition Table
δ 0 1 ε
q0 {q0 } − {q1 }
q1 − {q1 } {q2 }
q2 {q2 } {q2 } −

Find the ε - closure for q0 , q1 , q2

εc (q0 ) ={q0 , q1 , q2 }
εc (q1 ) ={q1 , q2 }
εc (q2 ) ={q2 }

160 / 184
Exercise 1
Extended transition function

δ̂(q0 , 0) = εc [δ(q0 , 0) ∪ δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [{q0 } ∪ ∅ ∪ {q2 }]
= εc [{q0 } ∪ {q2 }]
= εc [{q0 }] ∪ εc [{q2 }] = {q0 , q1 , q2 } ∪ {q2 }
δ̂(q0 , 0) = {q0 , q1 , q2 }

δ̂(q0 , 1) = εc [δ(q0 , 1) ∪ δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [∅ ∪ {q1 } ∪ {q2 }]
= εc [{q1 } ∪ {q2 }]
= εc [{q1 }] ∪ εc [{q2 }] = {q1 , q2 } ∪ {q2 }
δ̂(q0 , 1) = {q1 , q2 }

161 / 184
Exercise 1

δ̂(q1 , 0) = εc [δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [∅ ∪ {q2 }]
= εc [{q2 }]
δ̂(q1 , 0) = {q2 }

δ̂(q1 , 1) = εc [δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [{q1 } ∪ {q2 }]
= εc [{q1 }] ∪ εc [{q2 }] = {q1 , q2 } ∪ {q2 }
δ̂(q1 , 1) = {q1 , q2 }

162 / 184
Exercise 1

δ̂(q2 , 0) = εc [δ(q2 , 0)]

= εc [{q2 }]
δ̂(q2 , 0) = {q2 }

δ̂(q2 , 1) = εc [δ(q2 , 1)]

= εc [{q2 }]
δ̂(q2 , 1) = {q2 }

163 / 184
Exercise 1

Transition table for NFA

δ̂ 0 1
q0 {q0 , q1 , q2 } {q1 , q2 }
q1 {q2 } {q1 , q2 }
q2 {q2 } {q2 }

164 / 184
Exercise 1

Transition diagram for NFA

0 1 0,1

0,1 0,1
start q0 q1 q2

0,1

165 / 184
Exercise 1

NFA:
M = {Q, Σ, δ, q0 , F}

States Q = {q0 , q1 , q2 }

Inputs Σ = {0, 1}

Initial State q0 = q0 ∈ Q

Accept State F = {q2 } ⊆ Q

166 / 184
Exercise 2
Construct the following ε - NFA and find it’s equivalent DFA.

0 1 0,1

start q0 ε q1 ε q2

Solution:

M ={Q, Σ, δ, q0 , F}
Q ={q0 , q1 , q2 }
Σ ={0, 1, ε}
q0 ={q0 } ∈ Q
F ={q2 } ⊆ Q

167 / 184
Exercise 2

Transition Table
δ 0 1 ε
q0 {q0 } − {q1 }
q1 − {q1 } {q2 }
q2 {q2 } {q2 } −

Find the ε - closure for q0 , q1 , q2

εc (q0 ) ={q0 , q1 , q2 } =⇒ Let it be the state A

εc (q1 ) ={q1 , q2 } =⇒ Let it be the state B
εc (q2 ) ={q2 } =⇒ Let it be the state C

168 / 184
Exercise 2
Extended transition function

δ̂(A, 0) = εc [δ(q0 , 0) ∪ δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [{q0 } ∪ ∅ ∪ {q2 }]
= εc [{q0 } ∪ {q2 }]
= εc [{q0 }] ∪ εc [{q2 }] = {q0 , q1 , q2 } ∪ {q2 }
δ̂(A, 0) = {q0 , q1 , q2 } = A

δ̂(A, 1) = εc [δ(q0 , 1) ∪ δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [∅ ∪ {q1 } ∪ {q2 }]
= εc [{q1 } ∪ {q2 }]
= εc [{q1 }] ∪ εc [{q2 }] = {q1 , q2 } ∪ {q2 }
δ̂(A, 1) = {q1 , q2 } = B

169 / 184
Exercise 2

δ̂(B, 0) = εc [δ(q1 , 0) ∪ δ(q2 , 0)]

= εc [∅ ∪ {q2 }]
= εc [{q2 }]
δ̂(B, 0) = {q2 } = C

δ̂(B, 1) = εc [δ(q1 , 1) ∪ δ(q2 , 1)]

= εc [{q1 } ∪ {q2 }]
= εc [{q1 }] ∪ εc [{q2 }] = {q1 , q2 } ∪ {q2 }
δ̂(B, 1) = {q1 , q2 } = B

170 / 184
Exercise 2

δ̂(C, 0) = εc [δ(q2 , 0)]

= εc [{q2 }]
δ̂(C, 0) = {q2 } = C

δ̂(C, 1) = εc [δ(q2 , 1)]

= εc [{q2 }]
δ̂(C, 1) = {q2 } = C

171 / 184
Exercise 2

Transition table for DFA

δ̂ 0 1
A = {q0 , q1 , q2 } A = {q0 , q1 , q2 } B = {q1 , q2 }
B = {q1 , q2 } C = {q2 } B = {q1 , q2 }
C = {q2 } C = {q2 } C = {q2 }

172 / 184
Exercise 2

Transition diagram for DFA

0 1 0,1

1 0
start A B C

173 / 184
Exercise 2

DFA:
M = {Q, Σ, δ, q0 , F}

States Q = {A, B, C}

Inputs Σ = {0, 1}

Initial State q0 = q0 ∈ Q

Accept State F = {A, B, C} ⊆ Q

174 / 184
Minimization of DFA

Procedure:

Step 1: Remove unreachable states

Start from the initial state and see which states can be reached.

Delete any states that are not reachable.

Step 2: Partition the states into groups

Divide states into two groups:

1 Final states
2 Non-final states

175 / 184
Minimization of DFA

Step 3: Refine partitions

Within each group, check whether states are distinguishable:

Two states are distinguishable if, for some input string, one leads to a final
state while the other leads to a non-final state.

Keep splitting groups until no further refinement is possible.

Step 4: Construct the minimized DFA

Each group of equivalent states becomes a single state in the minimized

DFA.

Redraw transitions accordingly.

176 / 184
Example 1
Minimize the following DFA with C and D are the final states.

δ Input 0 Input 1
→A B C
B A D
C D A
D C B

Solution:
Given DFA
States: Q = {A, B, C, D}

Alphabet: Σ = {0, 1}

Start state: A

Final states: F = {C, D}

177 / 184
Example 1

Transition Diagram:
0

start A B

0
1 1 1 1
0

C D
0

178 / 184
Example 1

Step 1: Remove Unreachable States

From the start state A:

0 1
A→ − B and A → − C.
[i.e., B and C can be reached directly from the start state A]

From B and C we can reach D.

[i.e., D can be reached indirectly from the start state A using the states B
and C]
Thus all states {A, B, C, D} are reachable.
Conclusion: No states are removed.

179 / 184
Example 1

Step 2: Initial Partition

Partition states into final and non-final groups:

Final State group: {C, D}

Non-Final State group: {A, B}


P0 = {A, B}, {C, D} .

180 / 184
Example
Step 3: Refine Partitions

Check the non-final state group {A, B}:

On input 0: A → B, B → A (both stay in {A, B}).

On input 1: A → C, B → D (both go to {C, D}).

⇒ A and B behave identically; remain equivalent.

Check the final state group {C, D}:

On input 0: C → D, D → C (both stay in {C, D}).

On input 1: C → A, D → B (both go to {A, B}).

⇒ C and D behave identically; remain equivalent.

181 / 184
Example 1

No further split needed.

Final partition is: 

P = {A, B}, {C, D} .

Step 4: Construct the Minimized DFA

Each block becomes a single state:

Q′ = [A, B], [C, D]



start state [A, B]

final states {[C, D]}

182 / 184
Example 1

Transitions table for minimized DFA:

State Input 0 Input 1
[A, B] [A, B] [C, D]
[C, D] [C, D] [A, B]

Transation Diagram for minimized DFA:

0 0
1

start [A, B] [C, D]

183 / 184
Example 1

The minimized DFA:

M = {Q, Σ, δ, q0 , F}

States Q = [A, B], [C, D]

Input Σ = {0, 1}

Start state = [A, B]

Final state F = [C, D]

184 / 184