Introduction to

Theory of FA
Computation
Presented by: Loknath
Regmi
Assistant Professor,
Department of Electronics
and Computer Engineering
IOE, Pulchowk Campus
 FINITE AUTOMATA
• An automaton with a finite number of states is
called a Finite
Automaton (FA) or Finite State Machine (FSM).
• It is act as a recognizer for specific a
language/pattern.
• Any problem can be presented in form of decidable
problem
that can be answered by Yes/No.
• FA (machine with limited memory) can solve any
problem.
• Read an input string from tape
• Determine if the input string is in a language
• Determine if the answer for the problem is “YES” or
How does an FA
work
FA
 Formal definition of a Finite
Automaton
• 5-tuple (Q, Σ, δ, q0, F):
• Q 🡪finite non empty set of states.
• Σ 🡪finite set of symbols, called the
alphabet of the automaton. Σ
• δ 🡪transition
function.
• q 🡪initial state /start state from where any
0
input is processed (q0 ∈ Q).
• F 🡪set of final(accepting) state/states of Q
(F ⊆ Q).
FA
FA
 FA Representation for a
Language

L= Set of all strings starts with ‘a’

L={a, aa, ab, aba, abba, abbaa, . . .}
String w1= aba w2= baa
W1:aba
a. b a
A 🡪 B 🡪 B🡪 B (accepted)

W2:baa
b. a a
A 🡪 C🡪 C🡪 C (rejected)
37
 Types of FA
• DFA – Deterministic Finite Automata

• NFA- Non Deterministic Finite Automata

• ∈ NFA- NonDeterministic Finite Automata with
∈ Transtion
 DFA (Deterministic Finite
Automata)
• A Deterministic finite automaton DFA is a 5-tuple
If there is exactly one output
M = (Q, Σ, δ, q0, F) state in every transition
function of an automata, then
• Q is the set of states (finite)
the automata is called
• Σ is the alphabet (finite) Deterministic finite Automata
(DFA)
• δ:Q×Σ→Q is the transition
function

• q0 ∈ Q is the start state

• F ⊆ Q is the set of accept states

DFA
DFA-accepting example
DFA-Rejection example
DFA
DFA
M = (Q, Σ, δ, q0, F)
Q = {q0, q1, q2, DFA
qd} Σ = {0,1}
δ :Q×Σ→Q
q0 ∈ Q start state
F = { q2} ⊆ Q accept
state
DFA
Nondeterministic Finite
Automaton -NFA

• If there is zero or more output states in any of the

transition functions of an automata then that automata is
called Non-Deterministic Finite Automata (NFA).
• A Non-Deterministic finite automaton (NFA) is
represented by 5-tuples.
i.e. M = (Q, Σ, δ, q0, F)
• Q is a finite non-emptyset of states
• Σ is a finite non-empty set of symbols (An alphabet)
• δ: QX Σ → 2Q (subset of Q) is the transition function
• q0 ϵ Q is the start state
• F ϵ Q is a set of final states
Nondeterministic Finite
Automaton -NFA
Nondeterministic Finite
Automaton -NFA
• A nondeterministic finite automaton can be different from a
deterministic one in that
– for any input symbol, nondeterministic one can transit to
more
than one states.
– epsilon transition
 First Choice
For input “aa”
Second choice
NFA
 Difference between NFA and
DFA
• In DFA, For a given state on a given input we
reach to a deterministic and unique state.
• In NFA we may lead to more than one state for a
given input.
• Empty string can label transitions.
• We need to convert NFA to DFA for designing a
compiler.
 ∈-NFA
• If there is a transition symbol in NFA ,
forε then the
automata is called ε-NFA. finite automaton (NFA) is
🡪 An ε-Non-Deterministic
represented by [Link]
i.e. M = (Q, Σ, δ, q0, F)
• Q is a finite non-empty set of states
• Σ is a finite non-empty set of symbols (an alphabet)
• δ : QX (Σ U { ε })→ 2Q(subset of Q) is the transition
function
• q0 ϵ Q is the start state
• F ϵ Q is a set of final states
∈-NFA
 Acceptability by DFA and NFA

• Accepting String - S:
δ*(q0, S) ∈ F
• A string S′ is not accepted:
δ*(q0, S′) ∉ F
• Accepting language L :
{S | S ∈ ∑* and δ*(q0, S) ∈
F}
• The language L′ not accepted:
{S | S ∈ ∑* and δ*(q0, S) ∉
F}
Strings accepted :
{0, 00, 11, 010, 101, ...........}

Strings not accepted :

{1, 011, 111, ........}

 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
Step 1: L={110,1100,11010, …}
Step: 2
1
1 0
D
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0
D

0
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0
D

0 0
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0
D

0 0
1
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0
D

0 0
1
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0 D 0,1
0
0 1
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0 D 0,1
0
0 1

0,1
 Design a DFA
Accept all strings starting with “110”
Σ = {0,1}
L={110,1100,11010, …}

1
1 0 D 0,1
0
0 1
Example:1100
0,1
1 1 0 0
A🡪B🡪C🡪D🡪D
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
Step 1: L={010,0100,01010, …}
Step: 2
1
0 0
D
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0
D

1
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0
D

1 0
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0
D

1 0
1
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0
D

1 0
1
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0 D 0,1
1
0 1
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0 D 0,1
1
0 1

0,1
 Design a DFA
Accept all strings starting with “010”
Σ = {0,1}
L={010,0100,01010, …}

1
0 0 D 0,1
1
0 1
Example:1100
0,1
0 1 0 0
A🡪B🡪C🡪D🡪D
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
L={110,0110,110110, …}

1 1 0
D
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
L={110,0110,110110, …}

0 1 1 0
D
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
L={110,0110,110110, …}

0
0 1 1 0
D
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
L={110,0110,110110, …}

1
0
0 1 1 0
D
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
L={110,0110,11110, …}

1
0
0 1 1 0
D

0
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
L={110,0110,110110, …}

1
0
0 1 1 0
D

0
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
Example:0110
L={110,0110,110110, …}
0 1 1 0
A🡪A🡪B🡪C🡪D
1
0
0 1 1 0
D

0
 Design a DFA
Accept all strings ending with “110”
Σ = {0,1}
Example:0101
L={110,0110,110110, …}
0 1 0 1
A🡪A🡪B🡪A🡪B
1
0
0 1 1 0
D

0
 Design a DFA
Accept all strings ending with “01”
Σ = {0,1}
L={01,1101,01101,10101, …}

0 1
C
 Design a DFA
Accept all strings ending with “01”
Σ = {0,1}
L={01,1101,01101,10101, …}

1 0 1
C
 Design a DFA
Accept all strings ending with “01”
Σ = {0,1}
L={01,1101,01101,10101, …}

0
1 0 1
C

0
 Design a DFA
Accept all strings ending with “01”
Σ = {0,1}
Example:0101
L={01,1101,01101,10101, …}
0 1 0 1
A🡪B🡪C🡪B🡪C
0
1 0 1
C

1
 Design a DFA
Accept all substring with “11”

Σ = {0,1}
1.L={11,0110,11101, 101111,101110…}

1 1
C
 Design a DFA
Accept all substring with “11”

Σ = {0,1}
1.L={11,0110,11101, 101111,101110…}

0 1 1
C
 Design a DFA
Accept all substring with “11”

Σ = {0,1}
1.L={11,0110,11101, 101111,101110…}

0 1 1
C

0
 Design a DFA
Accept all substring with “11”

Σ = {0,1}
1.L={11,0110,11101, 101111,101110…}
0
0 1
1 C

0
 Design a DFA
Accept all substring with “11”

Σ = {0,1}
L={11,0110,11101, 101111,101110…}
0,1
0 1
1 C

Example:0110
0
0 1 1 0
A🡪A🡪B🡪C🡪C
 Design a DFA
Accept all substring with “11”

Σ = {0,1}
1.L={11,0110,11101, 101111,101110…}
0,1
0 1
1 C

Example:0100
0
0 1 0 0
A🡪A🡪B🡪A🡪A
 Design a DFA
Accept all substring not with “11”

Σ = {0,1}
1.L={11,0110,11101, 101111,101110…}
0,1
0 1
A 1B C

Example:0100
0
0 1 0 0
A🡪A🡪B🡪A🡪A
 Design a DFA , w ∈{a, b }, |w| ≥2

Σ = {a,b}
L={aa, ab, ba,bb, aaa,aab,aba,….}

a a
C
 Design a DFA , w ∈{a, b }, |w| ≥2

Σ = {a,b}
L={aa, ab, ba,bb, aaa,aab,aba,….}

a,b a,b
C
 Design a DFA , w ∈{a, b }, |w| ≥2

Σ = {a,b}
L={aa, ab, ba,bb, aaa,aab,aba,….}
a,b
a,b a,b
C

Example : abb
a b b
A🡪B🡪C🡪C
 Design a DFA , w ∈{a, b }, |w| = 2

• Σ = {a,b}
• L={aa, ab, ba,bb}

a a
C
 Design a DFA , w ∈{a, b }, |w| = 2

• Σ = {a,b}
• L={aa, ab, ba,bb}

a,b a,b
C
 Design a DFA , w ∈{a, b }, |w| = 2

• Σ = {a,b}
• L={aa, ab, ba,bb}

a,b a,b a,b

C
 Design a DFA , w ∈{a, b }, |w| = 2

• Σ = {a,b}
• L={aa, ab, ba,bb}
a,b
a,b a,b a,b
C

Example : abb
a b b
A🡪B🡪C🡪D
 Design a DFA , w ∈{a, b }, |w| ≤ 2
Σ = {a,b}
L={€, a, b, aa, ab, ba,
bb}
a,b a,b
A B C
 Design a DFA , w ∈{a, b }, |w| ≤ 2
Σ = {a,b}
L={€, a, b, aa, ab, ba,
bb}
a,b a,b a,b
A B C
 Design a DFA , w ∈{a, b }, |w| ≤ 2
Σ = {a,b}
L={€, a, b, aa, ab, ba, bb}
a,b
a,b a,b a,b
A B C

Example : abb
a b b
A🡪B🡪C🡪D
 Design a DFA , w ∈{a, b }, |w| mod 3 = 0

Σ = {a,b}
L={€, aba, bab, aaaaaa, bbbbbb...}

a,b a,b
A B

a,b
 Design a DFA , w ∈{a, b }, |w| mod 3 = 0

Σ = {a,b}
L={€, aba, bab, aaaaaa, bbbbbb...}

a,b a,b
A B

a,b
Example : abb
ab b
A🡪B🡪C🡪A
 Design a DFA , w ∈{a, b }, |w| mod 3 = 1

Σ = {a,b}
L={€, aba, bab, aaaaaa, bbbbbb...}

a,b a,b
A
B
B

a,b
Example : ababb
a b a b b
A🡪B🡪C🡪A🡪B🡪C
 Design a NFA
L={starts with ‘a’}

Σ = {a, b}
L={a, ab, aab ,. . .
}

a
A B
 Design a NFA
L={starts with ‘a’}

Σ = {a, b}
L={a, ab, aab ,. . . }
a,b
a
A B

Example : ab
a b
A🡪B🡪B
 Design a NFA
L={Contain ‘a’}

Σ = {a, b}
L={a, ba, abba ,. . . }

a
A B
 Design a NFA
L={Contain ‘a’}

Σ = {a, b}
L={a, ba, abba ,. . . }
a,b a,b

a
A B

Example : ab
a b
A🡪A 🡪A
B🡪B
 Design a NFA
L={Ends with ‘a’}

Σ = {a, b}
L={a, ba, bba ,. . . }

a
A B
 Design a NFA
L={Ends with ‘a’}

Σ = {a, b}
L={a, ba, bba ,. . . }
a,b
a
A B

Example : ba
b a
A🡪A🡪A
🡪B
Constructa DFA overalphabet{0,1} that accepts binary
string having evennumbers of Zeros and Even numbers of
1

5/4/2022
example
II

5/4/2022
How DFA process
strings?
• How DFA decides whether or not to “accept” a sequence of
input symbols ?
• The “language” of the DFA is the set of all symbols that the
DFA accepts.

5/4/2022
Extended Transition
Function of DFA
• We define the extended transition function ˆδ. It takes a state q
and an input string w to the resulting state. The definition
proceeds by induction over the length of w.

Basis step(w has length 0)

In this case, w is the empty string, i.e. the string of length 0, for
which we write Ɛ. We defin
e

5/4/2022
Induction step (from length l to length l + 1):

• In this case, w, which has length l + 1, is of the form va, where v is

a string of length l and a is a symbol. We define

•This works because, by induction hypothesis

is already defined

5/4/2022
Example:

5/4/2022
5/4/2022
Stringaccepted by
a DFA
• A string x is accepted by a DFA (Q, ∑, δ, q0, F) (q, x) = p ∈
if; F.

5/4/2022
Language of DFA
• The language of DFA M = (Q, ∑, δ, q0, F) denoted by L(M) is a set
of strings over ∑* that are accepted by M.

That is; the language of a DFA is the set of all strings w that take DFA starting from
start state to one of the accepting states. The language of DFA is called regular
language.

5/4/2022
Example:
1
• Construct a DFA, that accepts all the strings over ∑ = {a, b} that do
not end with ba.

5/4/2022
Example:2
DFA accepting all string over ∑ = {0, 1}
ending with 3 consecutive0’s

5/4/2022
Example:3
DFA over {a, b} accepting
{baa, ab, abb}

5/4/2022
Example:4
DFA accepting zero or more
consecutive 1’s.

5/4/2022
Example:5
DFA over {0, 1} accepting {1,
01}

5/4/2022
Example:5
DFA over {a, b} that accepts the strings
ending with abb

5/4/2022
Example:7
Create a DFA which accepts strings of odd
length

(∑ = {a, b}
)

5/4/2022
Example:8
• Design a DFA in which every 'a' should be followed by
'b' Given: Input alphabet, Σ={a, b}
Language L = {ε, ab, abab, bbbb, ...}

5/4/2022
Example:9
• Design a DFA in which every 'a' should never followed by
'b' Given: Input alphabet, Σ={a, b}
Language L = {ε, a, aa, aaa, ba, ...}

5/4/2022
Example:10
• Design a DFA Which accepts even numbers of ‘a’ and even
numbers of ‘b’

5/4/2022
Example:12 DFA: 0dd number
of1’s

5/4/2022
Example:13 DFA for {a, b}*{abb}

5/4/2022
Non-Deterministic Finite
Automata(NFA)

A deterministic finite automaton is defined by a quintuple (5-tuple) as (Q,

∑, δ, q0, F).
Where,
Q = Finite set of states,
∑ = Finite set of input symbols,
δ = A transition function that maps Q × ∑🡪2 𝑄
q0 = A start state; q0 ∈ Q
F = Set of final states; F ⊆ Q.

Unlike DFA, a transition function in NFA takes the NFA from one state
to several states just with a single input.

5/4/2022
5/4/2022
5/4/2022
Example:NFA over {0, 1} accepting
strings {0,01,11}

5/4/2022
Extended Transition
Function of NFA
• Basis: Without reading any input symbols, we are only in the state
we began in.

5/4/2022
 Induction
• Suppose w is a string of the form xa; that is ‘a’ is
the last symbol of w, and x is the string
consisting of all but not the last symbol.

Also suppose that

• Let,

5/4/2022
• We compute (q, w) by first computing (q, x) and by then
following any transition from any of these states that is labeled
a.

5/4/2022
Example: An NFA accepting
strings that end in 01

5/4/2022
NFA Practice:
• Construct a NFA over {a, b} that accepts strings having aa is
substring.

5/4/2022
NFA for strings over {0, 1} that
contain0110 or 1001.

5/4/2022
NFA over {a, b} that have a as
one of the last 3 characters.

5/4/2022
NFA over {a, b} that accepts
strings starting with a and
ending with b.

5/4/2022
E.g. Design a NFA for the
language over{0, 1} that
have at least two
consecutive 0’s or 1’s.

5/4/2022
Now, compute
10110;

5/4/2022
Language of
NFA
• The language of a NFA A = (Q, Σ, δ, q 0, F), denoted L(A) is defined
by:

• The language of A is the set of strings

contains at least one accepting state.
• The fact that choosing using the input symbols of w lead to a non-
accepting state, or do not lead to any state at all, does not prevent w
from being accepted by a NFA as a whole.

5/4/2022
 Equivalence of NFA and DFA
(Converting NFA to DFA)
Using Subset Construction Method
(Q = 2Q)
 Equivalence of NFA and DFA
(Converting NFA to DFA)
[Link] the language(if needed)
[Link] the transition diagram / table for NFA
3. Define NFA
4. Find the transition for DFA
1. Include the starting(initial) state of
NFA(q0) in DFA as starting state of DFA.
[Link] the transition for all the symbols
from q0.
[Link] the output state is new state, include it in
DFA and find the transition for all the
symbols from that state.
 Equivalence of NFA and DFA
(Converting NFA to DFA)
[Link] step- 4.3 until there are no more
new states
[Link] state which includes final state of NFA is
the final state of DFA
6. Draw the transition diagram/ table for DFA
7. Define DFA
[Link] the string acceptance by giving a simple
valid & Invalid inputs
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method
Solution:
[Link] the language
L ={01,001,101,1001,11101,101110101,…}
2.a Draw the transition diagram of NFA
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method

[Link] the transition diagram of NFA

2.b b. Draw the transition table of NFA

δN Input
0 1
🡪 q0 {q0,q1} {q0}
q1 Ǿ {q2}
* q2 Ǿ Ǿ

[Link] M =({q0,q1,q2},{0,1}, δN, q0,{q2})

NFA M =(Q,⅀, δ,q0,F)
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method

4. Find the transition function for DFA

[Link] the starting(initial) state of δN In
0
NFA(q0) in to a starting state of DFA
🡪q0 {q0,q1
}
🡪Initial State of DFA is q 0 q1 Ǿ
4.2 Find DFA transitions δD for 0,1 from q0 * q2 Ǿ

δD([q0],0)= {q0,q1} =[q0q1] 🡪New State

δD([q0],1)= {q0}= [q0] 🡪 Existing State
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method
4.3 Find DFA transitions δD for 0,1 from new
state

δD([q0 q1],0)= δ({q0},0)U δ({q1},0) δN Input

={q0 q1} U Ǿ = [q0q1] 🡪Existing State 0 1
🡪q0 {q0,q1} {q0
δD([q0 q1],1)= δ({q0},1)U δ({q1},1)
}
2 q ] 🡪New State
={q}0 U 2{q }0 =[q q1 Ǿ {q2
4.4 Repeat step 4.3 for new state }
* q2 Ǿ Ǿ
δD([q0q2],0) = δ({q0},0)U δ({q2},0)
={q0 q1} U Ǿ =[q0q1] 🡪Existing State
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method

4. Repeat step 4.3 for new state Input

δN
δD([q0q2],0) = δ({q0},0)U δ({q2},0) 0 1
🡪q0 {q0,q1} {q
={q0 q1} U Ǿ =[q0q1] 🡪Existing State
0
}
δD([q0q2],1) = δ({q0},1)U δ({q2},1 ) q1 Ǿ {q2
={q0} U Ǿ =[q0] 🡪Existing State }
* q2 Ǿ Ǿ
5. Final state of NFA is F={q2}
🡪 Final state of DFA is F=[q0q2]
5. a. Transition diagram for DFA

1 0
1
[q0 ] [q0 q1] [q0 q2]

0
1

b. Transition table for DFA

δD Input
0 1
🡪[q0] [q0q1] [q0]
[q0q1] [q0q1] [q0q2]
*[q0q2] [q0q1] [q0]
[Link] M’= =({[q0],[q0q1], [q0q2] },{0,1}, δD, [q0],{[q0q2]})
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method

7. String acceptance :
δD Input
a. Let w 1= 00101 0 1
δD([q0],00101) = δD([q0],00101) 🡪[q0] [q0q1] [q0]
[q0q1] [q0q1] [q0q2]
= δD([q0q1],0101)
*[q0q2] [q0q1] [q0]
= δD([q0q1],101)
= δD([q0q2],01)
= δD([q0q1],1)
= [q0q2] € F
the string w= 00101 is accepted by DFA
 Problem: Construct the DFA for the language L={w|w
ends in 01,w€{0,1}} using subset construction method
7. String acceptance :
b. Let w2 = 0010 δD Input
δD([q0],0010) = δD([q0],0010) 0 1
🡪[q0] [q0q1] [q0]
= δD([q0q1],010)
[q0q1] [q0q1] [q0q2]
= δD([q0q1],10)
*[q0q2] [q0q1] [q0]
= δD ([q
0 2q
],0)
= [q0q1] not in F
the string w= 00101 is not accepted by
DFA
 Problem:2 Convert NFA to DFA where 2nd symbol
from right hand side is ‘b’ over {a,b}

Solution:
[Link] the language
L ={ba,babb,aaba,baabbb…}
2.a. Draw the transition diagram of NFA
 Problem: Convert NFA to DFA where 2nd symbol from
right hand side is ‘b’ over {a,b}
[Link] the transition diagram of NFA
a/ a/
b b
A B C
b
2.b b. Draw the transition table of NFA
δN Input
a b
🡪A {A} {A,B}
B {C} {C}
*C Ǿ Ǿ
[Link] M =({A,B,C},{a,b}, δN, A,{C})
 Problem: Convert NFA to DFA where 2nd symbol from
right hand side is ‘b’ over {a,b}

4. Find the transition function for DFA δN

a
1. Initial State of DFA is q0 = A 🡪 A {A

[Link] DFA transitions δD for a,b from A B {C

*C Ǿ
δD([A],a)= {A} =[A] 🡪 Existing State

δD([A],b)= {A,B}= [AB] 🡪 New State

 Problem: Convert NFA to DFA where 2nd symbol from
right hand side is ‘b’ over {a,b}
[Link] DFA transitions δD for a,b from new state
δD([AB],a)= {A,C} = [AC] 🡪 New State δD([AB],b)=
{A,B,C} = [ABC] 🡪 New State δN Input
[Link] step 4.3 for new state δD([AC],a)= {A} a
🡪 A {A} {A
= [A] 🡪 Existing State δD([AC],b)= {A,B} =
B {C} {
[AB] 🡪 Existing State δD([ABC],a)= {A,C} = *C Ǿ
[AC] 🡪 Existing State

δD([ABC],b)= {A,B,C} = [ABC] 🡪 Existing State

5. Final state of NFA is F={C}
🡪 Final state of DFA is F={[AC],[ABC]}
 Problem: Convert NFA to DFA where 2nd symbol from
right hand side is ‘b’ over {a,b}
5. a. Transition diagram for DFAb
b
a
[A] [AB] b [AC] [ABC]
b a a

b. Transition table for DFA

δD Input
a b
🡪[A] [A] [AB]
[AB] [AC] [ABC]
*[AC] [A] [AB]
*[ABC] [AC] [ABC]

[Link] M’= =({[A],[AB], [AC] ,[ABC] },{a,b}, δD, [A],{[AC],[ABC]})

 Problem:3 Convert NFA to DFA
δN Input
0 1
🡪p {p,q} {p}
q {r} {r}
r {s} Ǿ
*s {s} {s}

1. Given NFA M = ({p,q,r,s},{0,1}, δN

p,{s})
2. Conversion from NFA to DFA :
δD Starts from Initial State : i.e., p
 Problem: Convert NFA to DFA

Find the transition function for DFA

δD([p],0)= {p,q} = [pq] 🡪 1st New State δN In
0
δD([p],1)= {p}= [p] 🡪 Existing State 🡪p {p,q}
q {r}
r {s}
δD([pq],0)= {p,q,r} = [pqr] 🡪 2nd New State *s {s}

δD([pq],1)= {p,r}= [pr] 🡪 3rd New State

δD([pr],0)= {p,q,s} = [pqs] 🡪4th New State
δD([pr],1)= {p}= [p] 🡪 Existing State
 Problem: Convert NFA to DFA

Find the transition function for DFA

δD([pqr],0)= {p,q,r,s} = [pqrs] 🡪 5th New State δN In

0
δD([pqr],1)= {p,r}= [pr] 🡪 Existing State 🡪p {p,q}
q {r}
r {s}
δD([pqs],0)= {p,q,r,s} = [pqrs] 🡪 Existing S tat *s {s}
δD([pqs],1)= {p,q,r,s} = [prs] 🡪 6th New State e

δD([prs],0)= {p,q,s} = [pqs] 🡪 Existing State

δD([prs],1)= {p,s}= [ps] 🡪 7th New state

 Problem: Convert NFA to DFA where 2nd symbol from
right hand side is ‘b’ over {a,b}
Transition table for DFA
δD Input
0 1
🡪[p] [pq] [p]
[pq] [pqr] [pr]
[pr] [pqs] [p]
[pqr] [pqrs] [pr]
*[pqs] [pqrs] [prs]
*[prs] [pqs] [ps]
*[ps] [pqs] [ps]
*[pqrs] [pqrs] [prs]

DFA M’= =({[p],[pq], [pr] ,[pqr] ,[pqs],[prs],[ps],[pqrs]},{0,1}, δD,

[p],{[pqs],[prs],[ps],[pqrs]})
 Exercise Problem: Convert NFA to DFA
1.
δN Input
0 1
🡪p {p,q} {p}
q {r,s} {t}
r {p,r} {s}
*s Ǿ Ǿ
*t Ǿ Ǿ

2. δN Input
0 1
🡪p {q,s} {q}
q {r} {q,r}
r {s} {p}
*s Ǿ {p}
 Finite Automata with Epsilon
Moves / Transition /NFA - ε /ε
-NFA

• Allowed to make transition without receiving

an input symbol,🡪 Epsilon moves
• It can be extended to included transition on empty
string 🡪
Extended NFA
Finite Automata with p Moves
(or) Ebsilon Transition (or) NFA
- ∈ (or)∈-NFA
• If there is a transition forε symbol in NFA
, then the automata is called ε-NFA.
• Represented by 5-tuples. i.e. M = (Q, Σ, δ, q0, F)
• Q 🡪finite non-empty set of states
• Σ 🡪 finite non-empty set of symbols (an alphabet)
• δ : QX (Σ U { ε })→ 2Q(subset of Q)is the transition
function
• q0 ϵ Q is the start state
• F ⊆ Q is a set of final states
 Finite Automata with Epsilon Moves (or)
Epsilon Transition (or) NFA - ε (or) ε -NFA

• Properti
es:
• 1.Ŝ(q , ε) = ε -closure(q)

• 2. Ŝ(q , a) = ε -closure(δ (Ŝ(q,

∈),a))
if w
• 3. Ŝ(q,w) = ε -closure(δ (Ŝ(q, =xa
x),a))
ε
-NFA
ε -closure(q)

• The ε -closure(q) is a set of all

states which are reachable from q on ε
-transition such that,

• i. ε -closure(q) = {q} where q €Q

• ii. If there exists ε -closure(q) = {r} and

δ (r, ε ) ={s} then ε -closure(q) ={r,s}

Find ε -closure() of each
state
0 1

q q1
0
ε
ε -closure(q0)
={q0,q1} ε
-closure(q1)={q1}
Find ε -closure() of each state

0 1

q q1
1
0

ε -closure(q0)
={q0} ε
-closure(q1)={
q1}
Find ε -closure() of each
state
a b c

q q1 q
0
ε a 2

ε -closure(q0)
={q0,q1} ε
-closure(q1)={q1}
ε
-closure(q2)={q2}
Find ε -closure() of each
state
a b c

q q1 q
0
ε ε 2

ε -closure(q0)
={q0,q1,q2} ε
-closure(q1)={q1,q2
}
ε -closure(q2)={q2}
Find ε -closure() of each
state
ε -closure(p)
={p,q,r,s }

ε -closure(q)={ q}

ε -closure(r)
={q,r}

ε -closure(s)={
q,r,s}
Find ε -closure() of each
state

q a r
ε ε
p u

ε s t ε
b
ε -closure(p) ε
={p,q,s } -closure(q)={
ε -closure(r)={ q}
r,u} ε -closure(s)
ε -closure(t)={ ={s}
t,u} ε
Language Acceptance by ε-NFA

• Language accepted by NFA(M) is the

set of all strings on ∑accepted by M

• L(M) = {w ∈ ∑*; Ŝ(q0,w)∩F≠Ø}

• i.Ɐ w ∈ L, Ŝ(q0,w)∩F≠Ø 🡪 string w is

accepted

• ii.Ɐ w ∈ L, Ŝ(q0,w)∩F=Ø 🡪 string w is not

accepted
• Problem:Find extended transition of 012
a b c

q q1 q
0
ε ε 2

• Step 1: Obtain ε -closure() of each

state
• ε -closure(q0) = {q0,q1,q2}
• ε -closure(q1)={q1,q2}
• ε -closure(q2)={q2}
Problem:Find extended transition of 012
Step 2: Find the prefix of input string • ε -closure(q0) =
Prefix(012)={ε,0,01,012} {q0,q1,q2}
• ε
Step 3: Find Ŝ -closure(q1)={q1,q2}
Ŝ(q0, ε) =ε -closure(q0)={q0 } • ε -closure(q2)={q2}

• Ŝ(q0, 0) =ε -closure(δ (Ŝ( q0, ε),0))

• = ε -closure(δ ({ q0,q1,q2},0))
• =ε -closure(δ (q0,0)U δ (q1,0)U δ
(q2,0))
• = ε -closure(q0)={ q0,q1,q2}
Problem:Find extended transition of 012
• ε -closure(q0) =
Ŝ(q0, 01) =ε -closure(δ (Ŝ( q0, 0),1)) {q0,q1,q2}
• = ε -closure(δ ({ • ε
-closure(q1)={q1,q2}
q0,q1,q2},1)) • ε -closure(q2)={q2}

• =ε -closure(δ (q0,1)U δ (q1,1)U δ

•
(q2,1))

= ε -closure(q1)={ q1,q2}
• Problem:Find extended transition of 012
• ε -closure(q0) =
• Ŝ(q0, 012) =ε -closure(δ (Ŝ( q0, {q0,q1,q2}
01),2)) • ε
• = ε -closure(δ ({ -closure(q1)={q1,q2}
• ε -closure(q2)={q2}
q1,q2},2))
• =ε -closure(δ (q1,2)U δ
(q2,2))
• =ε
-closure(q2)={
={q2}
q2} € F is accepted
by FA
Problem: Convert from ∈- NFA to NFA
δ ε a b c
🡪p {q} {p} Ǿ Ǿ

q {r} Ǿ {q} Ǿ

*r Ǿ Ǿ Ǿ {r}
 Step1 : Obtain ε-closure of each
state ε-closure(p) ={p,q,r}
δ ε a b c
🡪p
ε-closure(q) ={q,r} {q} {p} Ǿ Ǿ

ε-closure(r) ={r} q {r} Ǿ {q} Ǿ

*r Ǿ Ǿ Ǿ {r}

•
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(p, a) =ε -closure(δ (Ŝ( p, ε),a))
= ε -closure(δ ({ p,q,r},a))
=ε -closure(δ (p,a)U δ (q,a)U δ
(r,a))
=ε -closure({p}U {Ǿ}U {Ǿ})
= ε -closure(p)
={p,q,r}
Ŝ(p, a) ={ p,q,r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(p, b) =ε -closure(δ (Ŝ( p, ε),b))
= ε -closure(δ ({ p,q,r},b))
=ε -closure(δ (p,b)U δ (q,b)U δ
(r,b))
=ε -closure({Ǿ}U{q}U {Ǿ})
= ε -closure(q)
={q,r}
Ŝ(p, b) ={ q,r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(p, c) =ε -closure(δ (Ŝ( p, ε),c))
= ε -closure(δ ({ p,q,r},c))
=ε -closure(δ (p,c)U δ (q,c)U δ
(r,c))
=ε -closure({Ǿ}U{Ǿ}U {r})
= ε -closure(r)
={r}
Ŝ(p, c) ={ r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(q, a) =ε -closure(δ (Ŝ( q, ε),a))
= ε -closure(δ ({q,r},a))
=ε -closure(δ (q,a)U δ (r,a))
=ε -closure({Ǿ}U {Ǿ})
= ε -closure(Ǿ)
=Ǿ
Ŝ(q, a) =Ǿ
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(q, b) =ε -closure(δ (Ŝ( q,
ε),b))
= ε -closure(δ ({q,r},b))
=ε -closure(δ (q,b)U δ (r,b))
=ε -closure({q}U {Ǿ})
= ε -closure(q)
={q,r}
Ŝ(q, b) ={q,r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(q, c) =ε -closure(δ (Ŝ( q,
ε),c))
= ε -closure(δ ({q,r},c)
=ε -closure(δ (q,c)U δ (r,c))
=ε -closure({Ǿ}U {r})
= ε -closure(r)
={r}
Ŝ(q, c) ={r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(r,a) =ε -closure(δ (Ŝ( r,
ε),a))
= ε -closure(δ ({r},a)
=ε -closure(δ (r,a))
=ε -closure({Ǿ})
=Ǿ
Ŝ(r, a) =Ǿ
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(r,b) =ε -closure(δ (Ŝ( r,
ε),b))
= ε -closure(δ ({r},b)
=ε -closure(δ (r,b))
=ε -closure({Ǿ})
=Ǿ
Ŝ(r, b) =Ǿ
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(r,c)=ε -closure(δ (Ŝ( r,
ε),c))
= ε -closure(δ ({r},c)
=ε -closure(δ (r,c))
=ε –closure(r)
= {r}
Ŝ(r, c) ={r}
• Step 3: Draw NFA Transition
table
δ a b c
🡪p {p,q,r} Ŝ(p, a)
={p,q,r}
q Ŝ(p, b)
*r ={q,r}
Ŝ(p, c) ={r}
Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } ={q,r}
Ŝ(p, c) ={r}
q Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
*r ={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ŝ(q ,a) = Ǿ
*r Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ Ŝ(q ,a) = Ǿ
*r Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ {q,r} Ŝ(q ,a) = Ǿ
*r Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
δ a b c Ŝ(p, a)
={p,q,r}
🡪p {p,q,r} {q,r } {r} Ŝ(p, b)
={q,r}
q Ǿ {q,r} {r} Ŝ(p, c) ={r}
*r Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
δ a b c Ŝ(p, a)
={p,q,r}
🡪p {p,q,r} {q,r } {r} Ŝ(p, b)
={q,r}
q Ǿ {q,r} {r} Ŝ(p, c) ={r}
*r Ǿ Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ {q,r} {r} Ŝ(q ,a) = Ǿ
*r Ǿ Ǿ Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ {q,r} {r} Ŝ(q ,a) = Ǿ
*r Ǿ Ǿ {r} Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 4: Draw NFA Transition
Diagram
Ŝ(p, ={p,q,
a) r}
a c Ŝ(p, ={q,r
b b) }
Ŝ(p, ={r}
p q r c)
a, b, =Ǿ
b Ŝ(q =
Ŝ(r,a) ={q,r
c
,a)
Ǿ }
Ŝ(q =
Ŝ(r ,b)={r}
,b)
Ǿ
Ŝ
Ŝ(r,c)
a, (q,c)
={r}
b,c
• Step 4: Draw NFA Transition
Diagram
a c
b
p q r
a, b,
b c

a, b,c
NFA M = ({p,q,r},{a,b,c}, δ,p,{r})
Problem: Convert from ∈- NFA to NFA
δ ε a b c
🡪p {q} {p} Ǿ Ǿ

q {r} Ǿ {q} Ǿ

*r Ǿ Ǿ Ǿ {r}
 Step1 : Obtain ε-closure of each
state ε-closure(p) ={p,q,r}
ε-closure(q) ={q,r} ε a b c
δ
ε-closure(r) ={r} 🡪p {q} {p} Ǿ Ǿ

q {r} Ǿ {q} Ǿ

*r Ǿ Ǿ Ǿ {r}

•
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(p, a) =ε -closure(δ (Ŝ( p, ε),a))
= ε -closure(δ ({ p,q,r},a))
=ε -closure(δ (p,a)U δ (q,a)U δ
(r,a))
=ε -closure({p}U {Ǿ}U {Ǿ})
= ε -closure(p)
={p,q,r}
Ŝ(p, a) ={ p,q,r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(p, b) =ε -closure(δ (Ŝ( p, ε),b))
= ε -closure(δ ({ p,q,r},b))
=ε -closure(δ (p,b)U δ (q,b)U δ
(r,b))
=ε -closure({Ǿ}U{q}U {Ǿ})
= ε -closure(q)
={q,r}
Ŝ(p, b) ={ q,r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(p, c) =ε -closure(δ (Ŝ( p, ε),c))
= ε -closure(δ ({ p,q,r},c))
=ε -closure(δ (p,c)U δ (q,c)U δ
(r,c))
=ε -closure({Ǿ}U{Ǿ}U {r})
= ε -closure(r)
={r}
Ŝ(p, c) ={ r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(q, a) =ε -closure(δ (Ŝ( q, ε),a))
= ε -closure(δ ({q,r},a))
=ε -closure(δ (q,a)U δ (r,a))
=ε -closure({Ǿ}U {Ǿ})
= ε -closure(Ǿ)
=Ǿ
Ŝ(q, a) =Ǿ
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(q, b) =ε -closure(δ (Ŝ( q,
ε),b))
= ε -closure(δ ({q,r},b))
=ε -closure(δ (q,b)U δ (r,b))
=ε -closure({q}U {Ǿ})
= ε -closure(q)
={q,r}
Ŝ(q, b) ={q,r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(q, c) =ε -closure(δ (Ŝ( q,
ε),c))
= ε -closure(δ ({q,r},c)
=ε -closure(δ (q,c)U δ (r,c))
=ε -closure({Ǿ}U {r})
= ε -closure(r)
={r}
Ŝ(q, c) ={r}
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(r,a) =ε -closure(δ (Ŝ( r,
ε),a))
= ε -closure(δ ({r},a)
=ε -closure(δ (r,a))
=ε -closure({Ǿ})
=Ǿ
Ŝ(r, a) =Ǿ
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(r,b) =ε -closure(δ (Ŝ( r,
ε),b))
= ε -closure(δ ({r},b)
=ε -closure(δ (r,b))
=ε -closure({Ǿ})
=Ǿ
Ŝ(r, b) =Ǿ
• Step 2: Find extended transition
function of each
state on each input symbols
Ŝ(r,c)=ε -closure(δ (Ŝ( r,
ε),c))
= ε -closure(δ ({r},c)
=ε -closure(δ (r,c))
=ε –closure(r)
= {r}
Ŝ(r, c) ={r}
• Step 3: Draw NFA Transition
table
δ a b c
🡪p {p,q,r} Ŝ(p, a)
={p,q,r}
q Ŝ(p, b)
*r ={q,r}
Ŝ(p, c) ={r}
Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } ={q,r}
Ŝ(p, c) ={r}
q Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
*r ={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ŝ(q ,a) = Ǿ
*r Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ Ŝ(q ,a) = Ǿ
*r Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ {q,r} Ŝ(q ,a) = Ǿ
*r Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
δ a b c Ŝ(p, a)
={p,q,r}
🡪p {p,q,r} {q,r } {r} Ŝ(p, b)
={q,r}
q Ǿ {q,r} {r} Ŝ(p, c) ={r}
*r Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
δ a b c Ŝ(p, a)
={p,q,r}
🡪p {p,q,r} {q,r } {r} Ŝ(p, b)
={q,r}
q Ǿ {q,r} {r} Ŝ(p, c) ={r}
*r Ǿ Ŝ(q ,a) = Ǿ
Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ {q,r} {r} Ŝ(q ,a) = Ǿ
*r Ǿ Ǿ Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 3: Draw NFA Transition
table
Ŝ(p, a)
δ a b c ={p,q,r}
Ŝ(p, b)
🡪p {p,q,r} {q,r } {r} ={q,r}
Ŝ(p, c) ={r}
q Ǿ {q,r} {r} Ŝ(q ,a) = Ǿ
*r Ǿ Ǿ {r} Ŝ(q ,b)
={q,r}
Ŝ(q,c) ={r}
Ŝ(r,a) =Ǿ
Ŝ(r ,b) =Ǿ
Ŝ(r,c) ={r}
• Step 4: Draw NFA Transition
Diagram
Ŝ(p, ={p,q,
a) r}
a c Ŝ(p, ={q,r
b b) }
Ŝ(p, ={r}
p q r c)
a, b, =Ǿ
b Ŝ(q =
Ŝ(r,a) ={q,r
c
,a)
Ǿ }
Ŝ(q =
Ŝ(r ,b)={r}
,b)
Ǿ
Ŝ
Ŝ(r,c)
a, (q,c)
={r}
b,c
• Step 4: Draw NFA Transition
Diagram
a c
b
p q r
a, b,
b c

a, b,c
NFA M = ({p,q,r},{a,b,c}, δ,p,{r})
Problem: Convert the έ-NFA to DFA
Step1 : Obtain ε-closure of each
state ε-closure(q0) :
ε-closure(q0)
={q0}
ε-closure(q1) :
ε-closure(q1)
={q1,q2}
ε-closure(q2) :
ε-closure(q2) ={q2}
 Step1 : Obtain ε-closure of each
state ε-closure(q0) ={q0}
ε-closure(q1)
={q1,q2}
ε-closure(q2)
={q2}
•
• Step 2: Find extended transition
function of each state{q0,q1,q2} on each
input symbols {a,b}

Ŝ(q0, a) =ε -closure(δ (Ŝ( q0,

ε),a))
= ε -closure(δ (Ŝ( q0,
ε),a))

ε –closure(q0)
= ε -closure(δ ({q0
},a))
=ε -closure(q1)
={q1, q2}
• Step 2: Find extended transition
function of each state{q0,q1,q2} on each
input symbols {a,b}
Ŝ(q0, b)
=ε -closure(δ (Ŝ( q0, ε),b))
= ε -closure(δ (Ŝ( q0, ε),b))

ε –closure(q0)
= ε -closure(δ ({q0 },b))
=ε -closure(Ǿ)
=Ǿ
Ŝ(q0, b) = Ǿ
• Step 2: Find extended transition
function of each state{q0,q1,q2} on each
input symbols {a,b}

Ŝ(q1, a) =ε -closure(δ (Ŝ( q1,

ε),a))
= ε -closure(δ (Ŝ( q1,
ε),a))

ε –closure(q1)
= ε -closure(δ ({q1 ,q2},a))
=ε -closure(δ (q1 ,a)U δ ( q2,a))
= ε -closure({q1}U{Ǿ})
= ε -closure(q1) ={q1 ,q2}
Ŝ(q0, a) ={q1,q2}
• Step 2: Find extended transition
function of each state{q0,q1,q2} on each
input symbols {a,b}

Ŝ(q1, b) =ε -closure(δ (Ŝ( q ,

1
ε),b))
= ε -closure(δ (Ŝ( q1,
ε),b))

ε –closure(q1)
= ε -closure(δ ({q1
,q2},b))
=ε -closure(δ (q1 ,b)U δ (
q2,b))
= ε -closure({Ǿ}U{q0})
• Step 2: Find extended transition
function of each state{q0,q1,q2} on each
input symbols {a,b}
Ŝ(q2, b)
🡪 =ε -closure(δ (Ŝ( q2, ε),b))
🡪 = ε -closure(δ (Ŝ( q2, ε),b))

🡪 ε –closure(q2)
🡪 = ε -closure(δ (q2,b))
🡪 =ε -closure(q0)
🡪 ={q0}
🡪 Ŝ(q2, b) ={q0}
• Step 3: Draw NFA Transition
table
δ a b
Ŝ(q , a) 0
🡪q0 {q1,q2} Ǿ ={q1,q2} Ŝ
(q0, b) =Ǿ Ŝ
*q1 {q1,q2} {q0} (q1, a) =
{q1,q2}
q2 Ǿ {q0}
Ŝ(q1, b)=
{q0} Ŝ(q2,
a) = Ǿ Ŝ(q2,
b) = {q0}

NFA M = ({q0,q1,q2},{a,b}, δ,q0,{q1})

• Step 4: Convert NFA to DFA
δD Starts from Initial State : i.e., q0 δ a b
δD([q0],a) 🡪q0 {q1,q2} Ǿ
= {q1,q2} *q1 {q1,q2} {q0}
q2 Ǿ {q0}
= [q1q2] 🡪 1 New State
st

δD([q0],b)

=Ǿ
• Step 4: Convert NFA to DFA
δD([q1q2],a)= δ a b
{q1,q2}
• 🡪q0 {q1,q2} Ǿ
*q1 {q1,q2} {q0}
=δ(q1,a) U δ(q2,a)
q2 Ǿ {q0}
={q1,q2}U{Ǿ} ={q1,q2}

= [q1q2]🡪 Existing State

δD([q1q2],b)

= {q0}

= [q0]🡪 Existing State

• Step 5:Draw DFA Transition Table

δD a b
🡪[q0] [q1q2] Ǿ
*[q1q2] [q1q2] [q0]

• DFA M’ = ({[q0],[q1q2]},{a,b},
δD,[q0],{[q1q2]})
 Exercise Problem
• Convertε-NFA to DFA
8