CSE1008 - Theory of Computation

WIN SEM - 2024-25

Dr. K. Srinivasa Reddy

Professor
SCOPE, VIT-AP University
Module No. 1 Finite Automata (FA) 11 Hours
Mathematical preliminaries and notations-Finite Automata-Deterministic Finite
Automata – Non-Deterministic Finite Automata and equivalence with DFA -
Epsilon transitions – Minimization of Finite Automata and its applications.
Mathematical preliminaries and notations
Symbol:
• An atomic unit, such as a digit, character, etc.
• Sometimes a word.
• Formal languages does not deal with the “meaning” of the symbols.
• Example: 0, 1, 2, a, b, c

Alphabet - a finite set of symbols.

Notation:  [Sigma]
Example:
• Binary alphabet  ={0,1} with two symbols
• English alphabet  ={a,…,z} with all alphabet symbols
• Alphanumeric:  ={a-z, A-Z, 0-9}
• The set of all ASCII characters
• Alphabet should not contain Latin letters.
Mathematical preliminaries and notations

String – A finite sequence of concatenated symbols from .

Notation:
(a) Letters u, v, w, x, y, and z denote strings.
(b) Convention: concatenate the symbols.
(c) No spaces, commas used.

Examples:
• 0, 10 and 001, 0000  Strings over the binary alphabet  = {0,1}
• a, b, ab and aabab  Strings over alphabet  ={a, b}

A null string is a string with no symbols, usually denoted by epsilon (ε) or lambda (λ).
Mathematical preliminaries and notations
Length of the string: The number of symbols in a string.
• For a string w, length is represented by |w| .
• It can be the empty string (also called null string) it has no symbols.
Example
|00100| = 5
|aab| = 3
|ε| = 0
• Small case letters towards the beginning of the English alphabet denote symbols of an
alphabet. ∑ = {a, b, c}
• Small case letters towards the end of the English alphabet denote strings over an alphabet
i.e., u, v, x, y, z are strings.
Mathematical preliminaries and notations
Language: A set of strings over . [also called formal language]
Notation: L

• A set of formation rules that describe which strings formed from the alphabet of a formal
language are syntactically valid. (Grammars)

Example:
• {0, 00, 000, 101, ...} is an "infinite" language over the binary alphabet ∑ = {0, 1}.
• {aa, ab, ba, bb} is a finite language over ∑ = {a,b} having string length = 2.
• {000, 001, 010, 011, 100, 101, 110, 111} is a finite language over ∑ = {0,1} having string
length = 3.
Mathematical preliminaries and notations
Examples for Languages:

1. The set of strings of 0’s and 1’s with no two consecutive 1’s.
L = {ε, 0, 1, 00, 01, 10, 000, 001, 010, 100, 101, 0000, 0001, 0010, 0100, 0101, 1000, 1001,
1010, . . .}

2. Palindromes: Strings that read the same forward and backward over the alphabet {0,1} is an
infinite language.
L = {ε, 0, 1, 00, 11, 000, 010, 101, 0000, 1111,1101011 . . .}

3. The language of all strings consisting of n 0s followed by n 1s ( n ≥ 0)

L = { ε, 01, 0011, 000111, . . . }
Mathematical preliminaries and notations
Examples for Languages:
4. Programming language C:
Legal programs are a subset of the possible strings that can be formed from the
alphabet of the language (a subset of ASCII characters).

5. The set of strings with equal number 0s and 1s :

L = { ε, 01, 10, 0011, 0101, 1001, . . . }
6. Empty language - empty set of strings.
Notation: φ or ∅
NOTE:
• { ε }  The language consisting of only the empty string, is also a language
over any alphabet
• ∅ ≠ { ε } since ∅ has no strings and { ε } has one.
Mathematical preliminaries and notations
Language:
• The membership problem: Given a string x, whether x ε
L or not.
• Used for the precise definition of data formats and the
syntax of programming languages.
• Play a crucial role in the development of compilers.
• Regular languages, context-free languages, context-
sensitive languages, recursive languages (decidable),
recursively enumerable languages (semi-decidable)
• Formal language theory uses separate formalisms, automata,
to describe their recognizers.
Mathematical preliminaries and notations
Languages and Machines | Chomsky Hierarchy
Mathematical preliminaries and notations
Fundamental Definitions:
• Symbol
• Alphabet
• String
• Language

Notations
• ∑
• L
• Length of the String: |w|
• ɛ  Empty String
• ∅  Empty language
• ∅ ≠ { ε } since ∅ has no strings and { ε } has one.
• Types of languages and corresponding automata
Mathematical preliminaries and notations
String Operations:
1. Concatenation:
u= ab, v=bab, uv  abbab , vu= babab
2. Prefixes:
u is a prefix of v if there is a string w such that v = uw
v =101, then ε, 1, 10, 101 are prefixes of v
3. Suffixes:
u is a suffix of v if there is a string w such that v = wu.
v =101, then ε, 1, 01, 101 are suffixes of v
4. Substrings:
u is a substring of v if there are x and y such that v = xuy.
v=101, then ε, 0, 1, 10, 01, 101 are substrings of v
Note: prefix and suffix are special cases of substring.
Mathematical preliminaries and notations

5. Proper Prefix & Proper Suffix: A string ‘u’ is a proper prefix / suffix of string ‘v’ if ‘u’ is a
prefix / suffix of ‘v’ and u ≠ v.
u=101, ε, 1, 10, are proper prefixes of u
and ε, 1, 01, are proper suffixes of u

6. Powers of strings: For any string x and integer n ≥ 0, then xn is the string formed by
sequentially concatenating ‘n’ copies of x.

String x = 011, then

x0 = ε
x1 = 011
x2= 011011
x3= 011011011
Mathematical preliminaries and notations
7. Powers of alphabet:
The set of all strings over an alphabet denoted by
∑* = ∑0 U ∑1 U ∑2 U ∑3 U … = U∑k
• Σ is an alphabet
• Σ1 is a set of strings; its members are strings (each one of length 1)
• ∑k (for some integer k) to denote the set of strings with length k with symbols from ∑
• ∑k = { w | w is a string over ∑ and | w | = k}.
Example ∑ = {0,1}
• ∑0 = { ε }
• ∑1 = { 0,1}
• ∑2 = { 00, 11, 01, 10}
• ∑3 = { 000, 001, 010, 011, 100, 101, 110, 111}
∑ = {0}, then ∑*= {ε, 0, 00, 000, 0000, …}.
Mathematical preliminaries and notations

8. ∑* (Kleene star or Kleene Closure of the alphabet)

Contains all the strings that can be generated by iteratively concatenating symbols from ∑ any
number of times.

Example:
• ∑ = {a}, then ∑*= {ε, a, aa, aaa, aaaa, …}.
• ∑ = {a, b}, then ∑*= {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, baa,…}

Note:
 ∑ = ø {The empty set} then ∑*= { ε}
 ∑*= ∑**
 ∑* is infinite, infinitely many words each of finite length.
Mathematical preliminaries and notations
9. ∑+ (Positive Closure of the alphabet)
∑+ contains the set of all nonempty strings that can be generated by iteratively concatenating
symbols from ∑ any number of times.

∑ = {a,b}, then

∑*= {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa,…}

∑+= {a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa,…}
Mathematical preliminaries and notations
Properties / Operations on Languages:
1. Basic Set Operations:
{Union (U), Intersection (Ⴖ), Difference(-)
{a, ab, aaaa} U {bb, ab} = { a, ab, bb, aaaa }  Union
{a, ab, aaaa} ∩ {bb, ab} = { ab }  Intersection
{a, ab, aaaa} - {bb, ab} = { a, aaaa}  Difference

2. Complement:
Mathematical preliminaries and notations

Properties/Operations on Languages:

3. Reverse:
Mathematical preliminaries and notations

Properties/Operations on Languages:

4. Concatenation: The concatenation of languages L and M, denoted

L.M or just LM, is the set of strings that can be formed by taking any
string in L and concatenating it with any string in M.
Mathematical preliminaries and notations
Properties/Operations on Languages:
5. Star-Closure (Kleene *) The closure of a language L is denoted L∗ and represents the set of
those strings that can be formed by taking any number of strings from L, possibly with
repetitions (i.e., the same string may be selected more than once) and concatenating all of them.

 If L = { 0, 1 } then L∗ is all strings of 0 and 1

 If L = { 0, 11 } then L∗ consists of strings of 0 and 1 such that the
1 come in pairs, e.g., 011, 11110. But not 01011 or 101.
Mathematical preliminaries and notations
Properties/Operations on Languages:

6. Positive-Closure
Mathematical preliminaries and notations

Language =
Alphabet +
String +
Grammar (rules, syntax) +
Operations on languages
(concatenation, union, intersection, Kleene star)
Mathematical preliminaries and notations
Lexicographic ordering of Strings: Dictionary ordering, shorter strings precede longer strings.

Let L1 = {peach, apple, cherry} and L2 = {pie, cobbler, ɛ}. List the elements of L1L2 in
lexicographic order.

apple,
peach,
cherry,
applepie,
peachpie, • Listed the items shortest first.
cherrypie, • Within a given length, listed the items alphabetically.
applecobbler,
peachcobbler,
cherrycobbler
Mathematical preliminaries and notations

1. Let L = {w ɛ {a, b}* : |w| Ξ3 0}. List the first six elements in a lexicographic enumeration of L.
ɛ, aaa, aab, aba, abb, baa

2. L = {w ɛ {a, b}* : x ɛ {a, b}+ (w = axa)}.

• L is the set of strings over the alphabet {a, b} whose length is at least 3 and that start and
end with a.
• aba, and aaa are in L.
• ɛ, a, ab and aa are not in L.
Mathematical preliminaries and notations
Relevance of strings and languages for this course.

Consider decision problems. Decision problems are problems with Yes / No

answers.
Examples:
(a) Is an array sorted?
(b) Is x in that array A?
The membership problem / problem:
Given a string x, whether x ε L or not.
Mathematical preliminaries and notations

Applications of the Concepts

Are vast, and include:

• Text processing (editors, etc.)
• Compiler design
• Verification through model checking
• Many more real-world examples …..
Mathematical preliminaries and notations

String Operations Language Operations

• Concatenation • Basic Set Operations
• Prefix • Complement
• Suffix • Reverse
• Substring • Concatenation
• Proper prefix and Proper Suffix • Kleene Closure
• Powers of alphabet • Positive Closure
• Powers of String
• Kleene Star / Closure
• Positive Closure

Lexicographic ordering of Strings

Next: Finite State Machines | Finite State Automata

Finite State Machines / Finite State Automata
Machine: An apparatus using mechanical power and having several parts, each with a definite
function and together performing a task.
Or
Things we do mechanistically.

Machine: Singular Machines: Plural

Automaton: Singular Automata: Plural
Given ∑ = {0,1}, L= { x ε {0,1}* | x has even number of 0’s}, Design a machine to recognize the
language L.

String x= 01100110  4 0’s Valid ε L

1111  0 0’s Valid ε L
0011000  5 0’s, not belongs to language
Finite State Machines / Finite State Automata
How to do?
Scan the string from left to right, one symbol at a time. The result should be ready as
soon as the scanning stops.

 Before starting, check have you seen any zero’s?

No, 0 0’s, so it is even number of 0’s.
 When you have seen
 First 0, state of mind is “one 0”, i.e. “odd number of 0’s”.
 If the next symbol is a 1, then state remains as “odd number of 0’s”,
 If the next symbol is a 0, the state changes to “even number of zeros”
Finite State Machines / Finite State Automata
Example: 1011001
String 1 0 1 1 0 0 1
[Link] Zeros Even Even Odd Odd Odd Even Odd Odd
so far seen (0-0’s) (0-0’s) (1-0) (1-0) (1-0) (2-0’s) (3-0’s) (3-0’s)

Example: 101101

String 1 0 1 1 0 1
[Link] Zeros Even Even Odd Odd Odd Even Even
so far seen (0-0’s) (0-0’s) (1-0) (1-0) (1-0) (2-0’s) (2-0’s)
Finite State Machines / Finite State Automata
State representation of the process for any length string.
• Identify number of states required.
• Give unique state names.
• Identify initial state and final state

Circle is used to represent the state

Name
of the State names are written inside the circle
state
Finite State Machines / Finite State Automata

State representation of the process for any length string.

• Identify number of states required: 02
• Give unique state names: Seen Even 0’s, Seen Odd 0’s
• Initial state: Seen Even 0’s (Marked with Incoming Arrow, no origin)
• Final state: *****

Seen Seen
Even Odd
0’s 0’s
Finite State Machines / Finite State Automata

State representation of the process for any length string.

• Identify the actions for changing the state | stating in the same state.
• Actions are indicated with labelled edges.

Seen Seen
Even Odd
0’s 0’s
Finite State Machines / Finite State Automata

1
1
Seen 0 Seen
Even Odd
0’s 0’s
0

1
1
0
q0 q1

0
Renaming the states as q0 and q1
Finite State Machines / Finite State Automata
Identify the final state: Scanning is completed, Given string satisfies the condition, belongs that
language. Indicated with double circle.
1
1
0
q0 q1

0
Final State diagram
Given ∑ = {0,1}, L= { x ε {0,1}* | x has odd number of 0’s}, Design a machine to recognize the
language L.
1
1
0
q0 q1
q1

0
Finite State Machines / Finite State Automata
Design a machine / automata to recognize the language L, where L= { x ε {0,1}* | x has even
number of 0’s}.

1
1
0
q0 q1

0
State / Transition diagram
Design a machine / automata to recognize the language L, where L= { x ε {0,1}* | x has odd
number of 0’s}.
1
1
0
q0 q1
q1

0
Finite State Machines / Finite State Automata
1. Set of states - Q {q0, q1}
2. Input Alphabet - ∑ {0,1}
3. Rule for going from one state to another state is called state transition.
Transition Function δ : Q X ∑  Q
4. q0  start state
5. F  Final state (or set of final states) = {q0}
Finite State Machines / Finite State Automata
Transitions representing in the form of a Table
State Symbol seen Next state
q0 * 1 q0
q0 * 0 q1
q1 1 q1
q1 0 q0
State 0 ∑ 1
*q0 Q q1 q0
q1 q0 q1
Transition Table L= { x ε {0,1}* | x has even number of 0’s},
State 0 1
q0 q1 q0
*q1 q0 q1
Transition Table L= { x ε {0,1}* | x has odd number of 0’s},
→ indicates the initial state; ∗ indicates the final state
Finite State Machines / Finite State Automata
Problem Solving approach to design Finite State machines
• Identify
• ∑
• Strings as part of Language [Valid and Invalid]
• The states
• Initial (start) state
• Possible transitions on ∑ for every state.
• Final state(s)

• If null string is accepted by machine, then initial state will become one of the set of
Final State(s).

• Solution is either Transition diagram or Table

Finite State Machines / Finite State Automata
Given ∑ = {0,1}, L= { x ε {0,1}* | x has even number of 0’s and even number of 1’s}. Design a
machine to recognize the language L.
Strings: ε, 00, 11, 0011, 0101, 0110, 1010, 1100, 1001, etc.

Identify States:
Seen Even 0’s, Even 1’s
Seen Odd 0’s, Even 1’s
Seen Odd 0’s, Odd 1’s
Seen Even 0’s, Odd 1’s

δ 0 1
*q0 q1 q2
q1 q0 q3
q2 q3 q0
q3 q2 q1
Transition Diagram Transition Table
→ indicates the start state: q0 ∗ indicates the final state
Finite State Machines / Finite State Automata

L= {Even number of 0’s and Even number of 1’s} L= {Odd number of 0’s and Even number of 1’s}

L= {Odd number of 0’s and Odd number of 1’s} L= {Even number of 0’s and Odd number of 1’s}
Finite State Machines / Finite State Automata
Definition: Finite Automata / Deterministic Finite Automata (DFA): A Deterministic Finite
Automaton (DFA) is a 5-tuple
(Q, ∑, δ, q0, F) where
– Q is a finite set of states
– ∑ is an alphabet
– δ : Q × ∑→ Q is a transition function
– q0 ε Q is the initial state
– F ⊆ Q is a set of accepting states (or final states).
• In transition diagrams, the accepting states will be denoted by double circles.
• Q × Σ is the set of 2-tuples (q, a) with q ∈ Q and a ∈ Σ

Deterministic: On each input there is one and only one state to which the automaton can
transition from its current state otherwise it is called as Non-Deterministic.
Finite State Machines / Finite State Automata
Problem Solving approach to design Finite State machines / DFA / NFA
• Identify
• ∑
• Strings as part of Language [Valid and Invalid]
• The states
• Initial (start) state
• Possible transitions on ∑ for every state.
• Final state(s)

• If null string is accepted by machine, then initial state will become one of the set of
Final State(s).

• Solution is either Transition diagram or Table

• Processing of strings
Processing of Strings in DFA
Question: Is string w acceptable by the DFA?
Input: A word w in ∑*
Output: Accept / Reject w
Steps:
• Begin at the “start state” q0
• For every input symbol in the sequence w do
• Compute the next state from the current state, given the current input symbol in w and the
transition function. δ : Q X ∑  Q
• If after all symbols in w are consumed, and the current state is one of the final states (F) then
accept w; Otherwise, reject w.

Accepting a string: The entire input string is processed, and the last state reached is part of the
set of final states (F).
Rejecting a string: The entire input string is processed, and the last state reached is not part of
the set of final states (F).
Processing of Strings in DFA
∑ = {0,1}, L= { x ε ∑* | x has even number of 0’s}
M= {{q0,q1}, {0,1}, δ, q0, {q0}} where δ is given by
1
1
0
q0 q1
0
State diagram
Steps: a) w= 010001
q0  start state
δ(q0, 0) q1 [010001, current state is q1, next input is 1]
δ(q1, 1)  q1 [010001, current state is q1, next input is 0]
δ(q1, 0)  q0 [010001, current state is q0, next input is 0]
δ(q0, 0)  q1 [010001, current state is q1, next input is 0]
δ(q1, 0)  q0 [010001, current state is q0, next input is 1]
δ(q0, 1)  q0 [010001, current state is q0, input is consumed]
Current state is q0 which is in the set of the final states F= {q0}, so the string is Accepted.
Processing of Strings in DFA
∑ = {0,1}, L= { x ε ∑* | x has even number of 0’s}
M= {{q0,q1}, {0,1}, δ, q0, {q0}} where δ is given by
1
1
0
q0 q1
0
State diagram
Steps: b) w= 01001
q0  start state
δ(q0, 0)  q1 [01001, current state is q1, next input is 1]
δ(q1, 1)  q1 [01001, current state is q1, next input is 0]
δ(q1, 0)  q0 [01001, current state is q0, next input is 0]
δ(q0, 0)  q1 [01001, current state is q1, next input is 0]
δ(q1, 1)  q1 [01001, current state is q1, input is consumed]
Current state is q1 not in the set of final states F= {q0}, so the string is Rejected.
DFA Problems
1. Starting (prefix) with a substring Ending with a substring
2. Having Substring [consecutive / different]
3. Specific Problems
Practice Problems
1. ∑ = {0}, L= { x ε ∑* | x has odd number of 0’s}
{0, 000, 00000, …} = {0 n: n is odd}
String x= 000  3 - 0’s Valid ε L
0 1 - 0 Valid ε L
000000  6 - 0’s, does not Valid, ε L
How to do?
• Start scanning string from Left to right,
• Go over the string one symbol at a time, and when the scanning on string is stopped then
answer should be ready.
• Before starting, check have you seen any zeros? no, 0 0’s, so it is even number of 0’s.
• When you have seen first 0, state of mind is one 0, i.e. odd number of zeros, if we have seen 0
next, then state of mind is even number of 0’s, if we have seen 0 next, then state of mind is
odd number of 0’s.
Practice Problems
1. L= { x ε {0} * | x has odd number of 0’s}

Seen 0 Seen
Even Odd
0’s 0’s
0
w=000
String 0 0 0
No. of Zeros Even Odd Even Odd
So far seen (0-0’s) (1 -0) (2 – 0’s) (3–0’s)
Practice Problems
1. L= { x ε {0}, * | x has odd number of 0’s}

Seen 0 Seen
Even Odd
0’s 0’s
0

DFA M = {{q0,q1}, {0}, δ, q0, {q1}}

w=0000
String 0 0 0 0
No. of Zeros Even Odd Even Odd Even
So far seen (0-0’s) (1 -0) (2 – 0’s) (3–0’s) (4 – 0’s)
Now identify final state: Seen Even 0’s
Seen Odd 0’s
Practice Problems
2. L= { x ε {a, b} * : |x| <=2}
Allowed Strings in L= {ε, a, b, aa, ab, ba, bb}

a, b accept a, b aa, ab,aa,

accept ba,
ε a,
a, bb ab, bb
ba, bb

a, b
Reject
Practice Problems
3. ∑ = {a, b} L= { x ε {a, b} * : |x| =2}
Allowed Strings in L= {aa, ab, ba, bb}

a, b a, b aa, ab,aa,
accept ba,
a, b ab, bb
ba, bb

a, b
Reject
Practice Problems
4. L= { x ε {a, b} * : |x| >=2}

Allowed Strings in L= {aa, ab, ba, bb, aaa, abb, bbb, …..}

a, b a, b aa, ab,
a, b ba, bb
Practice Problems

5. ∑ = {a,b}, L = { } Empty Language

Only initial state no final state

6. ∑ = {a,b}, L = { ɛ } Empty String

7. ∑ = {a,b}, L = ∑*
Practice Problems
8. ∑ = {a, b}, L = {All strings with prefix ab}
Examples: ab, abb, aba, abbbbba, ….
Practice Problems
9. ∑ = {0,1}, L = {All binary strings containing substring 001}
Examples: 001, 1001, 000001, 01010100110101, ….
Practice Problems
10. ∑ = {0,1}, L={All binary strings not containing substring 001}
Examples: 0,1, 10,01, 000,010, ….
Practice Problems
11. ∑ = {0,1}, L={w|w has n 0’s where n mod 5 is 3. }
The language consists of all strings where the number of 0's is congruent to 3
modulo 5.

qi represents nmod5=i.
q3 is the accepting state, as it represents nmod5=3.
Transition Function:
δ(qi,0)=q(i+1)mod5
δ(qi,1)= qi
Problems
12. Design a DFA ‘M’ for the language L = {All strings whose binary
interpretation is divisible by 5}
• Reading a bit 𝑏, the state transitions based on the remainder when the current number
(calculated as the previous remainder shifted left by one bit, plus 𝑏) is divided by 5
δ(qi,b)=q(2i+b)mod5
where b is either 0 or 1.
q011
1
0 1 1
0

1 0 0
q0 q01 q010 q0100
0

Strings Accepted: 0, 101, 1010, 1111, 10100, 11001, 1000001 etc.

Problems
13. Design a DFA ‘M’ for the language L= {w ε {0, 1}* : w has a 1 in the third
position from the right}
Examples: 100, 101, 110, 111, 0101010101
1001011101110101010101
10010111011101010101011001011101110101010101
10010111011101010101011001011101110101010101
10010111011101010101011001011101110101010100
• Idea / Solution:
• How DFA knows that it has reached the third symbol from the right?
• Is the solution possible? YES | NO
• YES
• Hint: Remember the last three symbols that have been seen.
Problems
Idea / Solution:
• With three last symbols, the finite automaton has eight states, i.e. qijk, where i,
j, and k range over {0, 1}.
Idea / Solution:
• If the automaton is in state qijk, then the following hold:
• If M has read at least three symbols, then the three most recently read
symbols are ijk.
• If M has read only two symbols, then these two symbols are jk; moreover, i =
0.
• If M has read only one symbol, then this symbol is k; moreover, i = j = 0.
• If M has not read any symbol, then i = j = k = 0.
• So the initial state is q000 and the set of accept states are {q100, q110, q101, q111}.
Problems

Transition diagram of DFA ‘M’ for the language

L= {w ε {0, 1}* : w has a 1 in the third position from the right}
Practice Problems
14. L = {Set of all strings over {0, 1} which interpreted as binary number is
divisible by 4. }.

• q0 : Start state and accepting state, corresponding to divisible by 4. {0, 100, 1000…..}.
• q1 : For strings with the remainder 1 when divided by 4, that is {1, 101,……}.
• q2 : For strings with the remainder 2 when divided by 4, that is {10, 110,……}.
• q3 : For strings with the remainder 3 when divided by 4, that is {11, 111,……}.
Practice Problems
15. ∑ = {0,1}, L={w | w begins with 01 and ends with 01}
Problems
16. Design a DFA ‘M’ for the language L = {All strings have bbab as substring}
Exercise Problems
∑ = {0,1}, where L=
1. {w|w has two or three 1’s}
2. {w|w has an even number of 0’s and odd number of 1’s}
3. {w|w contains the substring 110}
4. {w|w does not contain the substring 110}
5. {w|w doesn’t contain neither of the substrings 11 and 00}
6. {w|w has exactly one occurrence of the substring 010. }
7. {w|w is a binary string that contains 01 as a substring}
8. {w|w is a binary string that contains 0 as third bit from right}
9. {w|w is a binary string that contains 1 as third bit from left}
Minimization of DFA | Minimize DFA
• The process of reducing a given DFA to its minimal form is known as minimization of DFA or
Optimization of DFA.
• The two popular methods for minimizing a DFA are-
Minimization of DFA

Equivalence Theorem Myhill Nerode Theorem

(Partition Method) (Table Filling Method)

The purpose of minimizing states in DFA :-

• To reduce the amount of space required to store the DFA.
• To simplify the understanding of the DFA's structure and improve the program's execution
speed.
• To achieve optimization by merging two or more equivalent states into a single state, resulting
in a smaller automaton that performs the same function as the original DFA.
Minimization of DFA | Minimize DFA
• There are certain states in a DFA that can be removed or merged without affecting the
language it accepts:
• Unreachable states : These are states that cannot be reached from the initial
state for any input string. Such states can be safely removed from the DFA.
• Dead states: These are states from which no final (accepting) state can be
reached. Dead states can be removed unless the DFA is required to be complete.
• Indistinguishable states: These are states that behave identically for all possible
input strings and cannot be distinguished from one another. Such states can be
merged into a single state.
Minimization of DFA | Minimize DFA
• Equivalent or Indistinguishable States
• Two states qi and qj are said to be equivalent (or indistinguishable) if, for every input
string, the machine transitions from both states to either a final state or a non-accepting
state consistently.
• Two states qi and qj are equivalent (or indistinguishable), if for all strings w ∈ Σ*
δ(qi, w) ∈ F ⇔ δ(qj, w) ∈ F
• Two states qi and qj are distinguishable, if for some string w ∈ Σ*
δ(qi, w) ∈ F ⇔ δ(qj, w) ∈ F
Minimization of DFA | Minimize DFA - Equivalence Theorem / Partition method

Step 1: Divide Q (set of states) into two sets. One set will contain all final states and other set
will contain non-final states. This partition is called P0.
Step 2: Initialize k = 1
Step 3: Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, take all possible pair
of states. If two states of a set are distinguishable, split the sets into different sets in Pk.
Step 4: Stop when Pk = Pk-1 (No change in partition)
Step 5: All states of one set are merged into one.

No. of states in minimized DFA will be equal to no. of sets in Pk.

How to find whether two states in partition Pk are distinguishable ?
Two states (qi, qj) are distinguishable in partition Pk if for any input symbol a, δ(qi, a) and δ(qj,a)
are in different sets in partition Pk-1.
Minimization of DFA | Minimize DFA - Equivalence Theorem
M = (Q, Σ, δ, q0, F), where Q = {1,2,...,9}, Σ = {a,b}, q0 = {1} F = {2,3,5}, and δ is as described in the table.
P0 = {{1,4,6,7,8,9}{2,3,5}}
For set {2,3,5} :
Pair a b Remarks

(2,3) (6,2) (8,1) Different Set / Same Set in P0, So, (2,3) are distinguishable.

(2,5) (6,2) (8,4) Different Set / Same Set in P0, So, (2,5) are distinguishable.

(3,5) (2,2) (1,4) Same Set / Same Set in P0, So, (3,5) are not distinguishable.

P1 = {{1,4,6,7,8,9}{2}{3,5}}
For set {1,4,6,7,8,9} in P0:
Pair a b Remarks

(1,4) (3,5) (7,7) Same Set / Same Set in P0, So, (1,4) are not distinguishable.

(1,6) (3,7) (7,9) Different Set / Same Set in P0, So, (1,6) are distinguishable.

(1,7) (3,3) (7,4) Same Set / Same Set in P0, So, (1,7) are not distinguishable.

(1,8) (3,4) (7,4) Different Set / Different Set in P0, So, (1,8) are distinguishable.

(1,9) (3,1) (7,8) Different Set / Different Set in P0, So, (1,9) are distinguishable.

P1 = {{1,4,7} {6,8,9}{2}{3,5}}
Minimization of DFA | Minimize DFA - Equivalence Theorem
P1 = {{1,4,7} {6,8,9}{2}{3,5}}
For set {1,4,7} in P1 :
Pair a b Remarks

(1,4) (3,5) (7,7) Same Set / Same Set in P1, So, (1,4) are not distinguishable.

(1,7) (3,3) (7,4) Same Set / Same Set in P1, So, (1,7) are not distinguishable.

For set {6,8,9} in P1:

Pair a b Remarks

(6,8) (7,4) (9,4) Same Set / Different Set in P1, So, (6,8) are distinguishable.

(6,9) (7,1) (9,8) Same Set / Same Set in P1, So, (6,9) are not distinguishable.

(8,9) (4,1) (4,8) Same Set / Different Set in P1, So, (8,9) are distinguishable.

P2 = {{1,4,7} {6,9} {8} {2} {3,5}}

For set {3,5} in P1:

Pair a b Remarks

(3,5) (2,2) (1,4) Same Set / Same Set in P1, So, (3,5) are not distinguishable.

P2 = {{1,4,7} {6,9} {8} {2} {3,5}}

Minimization of DFA | Minimize DFA - Equivalence Theorem
P2 = {{1,4,7} {6,9} {8} {2} {3,5}}
For set {1,4,7} in P2:
Pair a b Remarks

(1,4) (3,5) (7,7) Same Set / Same Set in P2, So, (1,4) are not distinguishable.

(1,7) (3,3) (7,4) Same Set / Same Set in P1, So, (1,7) are not distinguishable.

P3 = {{1,4,7} {6,9} {8} {2} {3,5}}

For set {6,9} in P3:
Pair a b Remarks

(6,9) (7,1) (9,8) Same Set / Different Set in P2 So, (6,9) are distinguishable.

P3 = {{1,4,7} {6} {9} {8} {2} {3,5}}

For set {3,5} in P3:
Pair a b Remarks

(3,5) (2,2) (1,4) Same Set / Same Set in P2, So, (3,5) are not distinguishable.

P3 = {{1,4,7} {6} {9} {8} {2} {3,5}}

Minimization of DFA | Minimize DFA - Equivalence Theorem
P3 = {{1,4,7} {6} {9} {8} {2} {3,5}}
For set {1,4,7} in P3:
Pair a b Remarks

(1,4) (3,5) (7,7) Same Set / Same Set in P2, So, (1,4) are not distinguishable.

(1,7) (3,3) (7,4) Same Set / Same Set in P1, So, (1,7) are not distinguishable.

P4 = {{1,4,7} {6} {9} {8} {2} {3,5}}

For set {3,5} in P3:

Pair a b Remarks

(3,5) (2,2) (1,4) Same Set / Same Set in P2, So, (3,5) are not distinguishable.

P4 = {{1,4,7} {6} {9} {8} {2} {3,5}}

P4 = P3, Stop the Process

Merge the states {1,4,7} as single state and {3,5} as single state.
Minimization of DFA | Minimize DFA - Equivalence Theorem

DFA

Minimized
DFA

Minimized DFA
Minimization of DFA | Minimize DFA - Equivalence Theorem State 0 1
q0 q3 q1
*q1 q2 q5
*q2 q2 q5
q3 q0 q4
*q4 q2 q5
q5 q5 q5
Step 1. P0 will have two sets of states, which are final states and non final states of DFA. P0 = { { q1, q2, q4 }, { q0, q3, q5 } }.
Step 2. To calculate P1, check whether sets of partition P0 can be partitioned or not.
i) For set { q1, q2, q4 } in P0 :
Pair 0 1 Remarks
(q1, q2) (q2, q2) (q5, q5) Same Set / Same Set in P0, So, (q1, q2) are not distinguishable.
(q1, q4) (q2,q2) (q5, q5) Same Set / Same Set in P0, So, (q1, q4) are not distinguishable.
(q2, q4) (q2, q2) (q5, q5) Same Set / Same Set in P0, So, , (q2, q4) are not distinguishable.
ii) For set { q0, q3, q5 } in P0 :
Pair 0 1 Remarks
(q0, q3) (q3, q0) (q1, q4) Same Set / Same Set in P0, So, (q0, q3) are not distinguishable.
(q0, q5) (q3, q5) (q1, q5) Same set / Different Set in P0 So, (q0, q5) are distinguishable.
(q3, q5) (q0, q5) (q4, q5) Same set / Different Set in P0, So, (q3, q5) are distinguishable.

P1 = { { q1, q2, q4 }, { q0, q3}, { q5 } }

Minimization of DFA | Minimize DFA - Equivalence Theorem State 0 1
P1 = { { q1, q2, q4 }, { q0, q3}, { q5 } } q0 q3 q1
To calculate P2, check whether sets of partition P1 can be partitioned or not: *q1 q2 q5
iii) For set {q1, q2, q4 } in P1:
*q2 q2 q5
Pair 0 1 Remarks
q3 q0 q4
(q1, q2) (q2, q2) (q5, q5) Same Set / Same Set in P1, So, (q1, q2) are not distinguishable.
*q4 q2 q5
(q1, q4) (q2, q2) (q5, q5) Same Set / Same Set in P1, So, (q1, q4) are not distinguishable.
q5 q5 q5
(q2, q4) (q2, q2) (q5, q5) Same Set / Same Set in P1, So, (q2, q4) are not distinguishable.
iv)For set { q0, q3 } in P1
Pair 0 1 Remarks
(q0, q3) (q3, q0) (q1, q4) Same Set / Same Set in P1, So, (q0, q3) are not distinguishable.
v) For set { q5 } : Since, only one state in this set, it can’t be further partitioned.
So, P2 = { { q1, q2, q4 }, { q0, q3 }, { q5 } } = P1
In P2, {q1, q2, q4} states are merged into one state. Similarly, {q0, q3} are merged into one state.

Minimized DFA
Minimization of DFA | Minimize DFA - Equivalence Theorem
State 0 1
q0 q1 q3
q1 q2 q4
q2 q1 q4
q3 q2 q4
*q4 q4 q4
Initially 0-equivalence  P0 = {{ q0,q1,q2,q3}, { q4 }}
Pair 0 1 Remarks
(q0, q1) (q1, q2) (q3, q4) Same Set / Different Set in P0, So, (q0, q1) are distinguishable.
(q0, q2) (q1, q1) (q3, q4) Same Set / Different Set in P0, So, (q0, q2) are distinguishable.
(q0, q3) (q1, q2) (q3, q4) Same Set / Different Set in P0, So, (q0, q3) are distinguishable.
P1 = {{ q0}, {q1,q2,q3}{ q4 }}
Pair 0 1 Remarks
(q1, q2) (q2, q1) (q4, q4) Same Set / Same Set in P0, So, (q1, q2) are not distinguishable.
(q1, q3) (q2, q2) (q4, q4) Same Set / Same Set in P0, So, (q1, q3) are not distinguishable.
(q2, q3) (q1, q2) (q4, q4) Same Set / Same Set in P0, So, (q2, q3) are not distinguishable.
P2 = {{ q0}, {q1, q2, q3}{ q4 }} Minimized DFA
DFA Minimization Algorithm Myhill-Nerode theorem – Table filling Method
A state is said to be unreachable if on no input the DFA ever traverses that state.
Let D = (Q, Σ, δ, q0, F) be a DFA that does not have any unreachable states.
The algorithm to minimize the DFA is as follows:
1. Create a table of pairs {p, q}, where p, q ∈ Q. All entries of the table are initially unmarked.
2. Mark the pair {p, q} if p ∈ F and q ∈ F, or vice versa.
3. Repeat the following until an entire pass of the table and no new pair gets marked:
• If {p, q} is unmarked and there exists a symbol a ∈ Σ such that {δ(p, a), δ(q, a)} is
marked, then mark pair {p, q}.
4. After completion, p ≈ q if and only if {p, q} is not marked.
DFA Minimization Algorithm Myhill-Nerode theorem - Table filling Method
M = (Q, Σ, δ, q0, F), where Q = {1,2,...,9}, Σ = {a,b}, q0 = {1}, F = {2,3,5}, and δ is as described in the table to the right.

1
2 2

3 Remove 3
4 these cells 4
5 5
6 6
7 7
8 8
9 9
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
DFA Minimization: Myhill-Nerode theorem - Table filling Method

2 X
Mark the pair {p, q} if p ∈ F and q ∈ F, or vice versa.
3 X
F = {2,3,5}
4 X X
5 X X
6 X X X
7 X X X
8 X X X
9 X X X
1 2 3 4 5 6 7 8
Mark the (P, Q) state if any unmarked state pairs exist δ(P, x), δ(Q, x) is marked. Continue until no more markings are possible.
DFA Minimization: Myhill-Nerode theorem - Table filling Method
2 X Unmarked pair (δ(P, x), δ(Q, x)) (δ(P, x), δ(Q, x))
(P, Q) x=a x=b
3 X X
(4, 1) (5, 3) – not marked (7, 7) – not exist
4 X X (6, 1) (7, 3) – marked, So Mark (6, 1) -
5 X X X (7, 1) (3, 3) – not exist (4, 7) – not marked
6 X X X X X (8, 1) (4, 3) – marked, So Mark (8, 1) -
7 X X X X (9, 1) (1, 3) – marked, So Mark (9, 1)
8 X X X X X X X (3, 2) (2, 6) - marked, So Mark (3, 2)

9 X X X X X X X (5, 2) (2, 6) – marked, So Mark (5, 2)

(5, 3) (2, 2) – not exist (1, 4) – not marked
1 2 3 4 5 6 7 8
(6, 4) (7, 5) – marked, So Mark (6, 4) -
(7, 4) (3, 5) – not marked (4, 7) - not marked
(8, 4) (4, 5) – marked, So Mark (8, 4) -
Mark the (P, Q) state if any unmarked state pairs exist (9, 4) (1, 5) – marked, So Mark (9, 4) -
(δ(P, x), δ(Q, x)) is marked. Continue until no more (7, 6) (3, 7) – marked, So Mark (7, 6)
markings are possible. (8, 6) (4, 7) – not marked (4, 9) marked, So Mark (8, 6)
(9, 6) (1, 7) – not marked (8, 9) - not marked
(8, 7) (4, 3) – marked, So Mark (8, 7) -
(9, 7) (1, 3) – marked, So Mark (9, 7) -
(9, 8) (1, 4) – not marked (8, 4) - marked, So Mark (9, 8)
DFA Minimization: Myhill-Nerode theorem - Table filling Method
Unmarked pair (δ(P, x), δ(Q, x)) (δ(P, x), δ(Q, x))
2 X (P, Q) x=a x=b
3 X X (4, 1) (5, 3) – not marked (7, 7) – not exist
4 X X (7, 1) (3, 3) – not exist (4, 7) – not marked
5 X X X (5, 3) (2, 2) – not exist (1, 4) – not marked

6 X X X X X (7, 4) (3, 5) – not marked (4, 7) - not marked

(9, 6) (1, 7) – not marked (8, 9) - marked, So Mark (9,6)
7 X X X X
8 X X X X X X X
Unmarked pair (δ(P, x), δ(Q, x)) (δ(P, x), δ(Q, x))
9 X X X X X X X X (P, Q) x=a x=b
1 2 3 4 5 6 7 8 (4, 1) (5, 3) – not marked (7, 7) – not exist
(7, 1) (3, 3) – not exist (4, 7) – not marked
(5, 3) (2, 2) – not exist (1, 4) – not marked
Mark the (P, Q) state if any unmarked state pairs exist
(7, 4) (3, 5) – not marked (4, 7) -- not marked
δ(P, x), δ(Q, x) is marked. Continue until no more
markings are possible.

• Make a single state in the minimized DFA by combining all the unmarked pairings.
• The unmarked pairs are (4, 1), (7, 1), (7, 4), and (5, 3).
• Now let's combine the unmarked pairs. (1, 4, 7) as single state and (3, 5) as single state.
Minimization of DFA | Minimize DFA - - Table filling Method

DFA

Minimized
DFA
Minimization of DFA | Minimize DFA

P0 = {{q3,q4} {q0,q1,q2}}
P1 = {{q3,q4} {q0}, {q1,q2}} Minimized DFA
P2 = {{q3,q4} {q0}, {q1,q2}}
P1 = P2

P0 = { { 3 } , { 1 , 2 , 4 , 5 , 6 } }.
P1 = { { 3 } , { 1 , 4 , 5 } , { 2 , 6 } }
P2 = { { 3 } , { 1 , 4 } , { 5 } , { 2 } , { 6 } }
P3 = { { 1 } , { 2 } , { 3 } , { 4 } , { 5 } , { 6 } }

The number of states of the given DFA is already minimum and it can
not be reduced any further.
Minimization of DFA | Minimize DFA
The states q7 and q8 are unreachable states.
Remove them before minimization of DFA.

DFA

Minimized DFA
Minimization of DFA | Minimize DFA

State a b c PF = {1,5}, {7,9}, {4}, {2}, {3}, {6}, {8}}

*1 2 6 -
2 - 5 3
3 - 4 3
*4 3 - -
*5 2 6 -
6 - - 7
*7 8 6 -
8 - 9 -
*9 8 6 -
Minimization of DFA | Minimize DFA
Extended Transition Function (δ* or δ^ )

Implies that there is a walk of transitions

q w q

Special case: for any state q, δ*(q, ε)  q

Processing of Strings in DFA using δ*
Steps: a) w= 010 for ∑ = {0,1}, L= { x ε {0,1}* | x has even number of 0’s}
• q0  start state
• δ*(q0, 010)  δ*(δ(q0, 0),10)δ*(q1, 10) [state is q1, next input is 1]
• δ*(q1, 10)  δ*(δ(q1, 1),0)δ*(q1, 0) [state is q1, next input is 0]
• δ*(q1, 0)  δ*(δ(q1, 0),ɛ)δ*(q0, ɛ) [state is q0, no input]
• δ*(q0, ɛ)  q0
• Current state is q0 which is in the set of the final states F= {q0}, so the string is Accepted.

1
1
0
q0 q1

0
State diagram
Processing of Strings in DFA using δ*
Steps: a) w= 011 for ∑ = {0,1}, L= { x ε {0,1}* | x has even number of 0’s}
• q0  start state
• δ*(q0, 01)  δ*(δ(q0, 0),1)δ*(q1, 1) [state is q1, next input is 1]
• δ*(q1, 1)  δ*(δ(q1, 1), ɛ)δ*(q1, ɛ) [state is q1, next input is ɛ]
• δ*(q1, ɛ)  q1
• Current state is q1 which is not in the set of the final states F= {q0}, so the string is Rejected.

1
1
0
q0 q1

0
State diagram
Language of DFA M:
It is denoted as L(M) and contains all the strings accepted by M.
For a DFA M= (Q, ∑, δ, q0, F)
The language of a DFA is the set
of all strings over Σ that, starting
these languages are called Regular Languages. from q0 and following the
transitions as the string is read
left to right, will reach some
accepting state.
Language accepted by DFA

Language rejected by DFA

Non-Deterministic Finite Automata(NFA)
• Given a current state of the machine and input symbol to be read, the next state is not uniquely
determined. Implying that the machine can exist in more than one state at the same time.
• Outgoing transitions could be non-deterministic.
• Each transition function maps to a set of states.
• Could a non-deterministic state machine be implemented in practice?
Yes E.g., toss of a coin, a roll of dice
• Nondeterminism in Computer Science is not so much about guessing as having a number of viable
choices available at some point and not knowing which choice "leads to a solution."
• A deterministic procedure that performs f(n) steps always
finishes in f(n) steps and always returns the same result.
• A non-deterministic procedure that has f(n) levels might
not return the same result on different runs.
• Nondeterminism via Computation Tree
• Think of Non-determinism as a tree growing
downwards, with the children of a node its possible
successors.
• (The input is accepted exactly when at least one of
the branches ends in an accept state)
Nondeterminism as “Guess and Finite
Non-Deterministic Verify”:Automata(NFA)
• There are many ways to view Nondeterminism.
• One way is the “guess and verify” idea: We assume the NFA is clairvoyant and
always guesses correctly the next state to go to. However, the NFA must
“check” its guesses.
• Clairvoyant: A person who claims to have a supernatural ability to perceive
events in the future or beyond normal sensory contact.
Why Non-Deterministic Finite Automata (NFA)
• NFAs accept exactly the same languages just as DFA’s
• However, there are reasons to think about NFAs
• They are often more concise and easier to design than DFAs
• Convert an NFA to a DFA the latter may have exponentially more states
than the NFA

NFAs have 3 features when compared with DFAs.

1. Ability to take a step without reading any input symbol (ɛ-NFA).
2. A state may have no transition on a particular symbol.
3. Ability to transition to more than one state on a given symbol
Non-Deterministic Finite Automata(NFA)
Nondeterminism: ε-transitions
• ε-transitions are allowed: arrows labeled with the empty string. These allow the NFA to
change state without consuming an input symbol.
• Example: Spelling of “color” is “colour”.
• In a web search application, you may want to recognize both variants.

• More Examples
• to, too, two
• Acknowledgment / Acknowledgement
Non-Deterministic Finite Automata(NFA)
Nondeterminism: No transitions

• No 0-transition out of initial state

• In the above automaton, if the string starts with a 0
then the string has no computation (i.e., rejected).
Non-Deterministic Finite Automata(NFA)

Nondeterminism: Multiple transitions

NFA Accepting any binary string that contains 00 or 11 as a substring.

Non-Deterministic Finite Automata(NFA)
Consider the transition diagram of NFA for L= {All strings ends with 10}

L= All strings ends with 10

W = 11010 1 1 0 1 0

1 1 1

0 0

Accept
Non-Deterministic Finite Finite
Non-Deterministic Automata(NFA)
Automata(NFA)
• In a Non-deterministic Finite Automaton (NFA), each state can have zero, one,
two, or more transitions corresponding to a given input symbol.
• For any input symbol, a state may have multiple transitions leading to different
states, creating branching paths.
• When an NFA encounters an input symbol at a given state, it may have multiple
possible transitions. These different transitions are referred to as branches.
• If an input symbol leads to multiple transitions from the same state, the NFA
explores all possible branches simultaneously.
• An NFA accepts an input string if there exists at least one sequence of transitions
(a branch) that leads to an accepting state. Therefore, the NFA needs only one
successful branch to accept the string.
• However, for the NFA to reject an input string, every possible branch must end
in a non-accepting state.
Non-Deterministic Finite Automata(NFA)
1.L= {w ε {0, 1}* : w has a 0 in the third position from the right}

No. of States in NFA are : 04

Equivalent DFA will have 08 states, 04 are final states.
2. L= {w ε {0, 1}* : w ends with 101}
Non-Deterministic Finite Automata(NFA)
3. Design an NFA for L= {The set of all binary strings that have either the number of 0’s odd, or
the number of 1’s not a multiple of 3, or both.}

4. Design a NFA for L= {Set of strings where the length is either a multiple 2 or 3}
Non-Deterministic Finite Automata(NFA)
Definition: An NFA is represented formally by a 5-tuple, (Q, Σ, δ, q0, F), consisting of
• Q a finite set of states
• Σ a finite set of input symbols
• δ a transition function Q × (Σ ∪ { ε }) → P(Q)
• q0 (q0 ∈ Q) an initial (or start) state
• F ⊆ Q a set of final states
• Here, P(Q) denotes the Power set of Q (2Q). In case of NFA, from a state, transition can
occur to any combination of Q states.
Power set: If S is the set {x, y, z}, then the subsets of S are power set of S is {{}, {x}, {y}, {z},
{x, y}, {x, z}, {y, z}, {x, y, z}}.
Non-Deterministic Finite Finite
Non-Deterministic Automata(NFA)
Automata(NFA)
Given Σ = {0, 1, 2}, Design NFA for language L = {w#c | w ∈ Σ*, c ∈ Σ, and c occurs in w}
Ex:
1011#0 ∈ L
1011#2 ∈ L
Solution:
• Read symbols of w, i.e., portion of
input before # is seen
• Guess at some point that current
symbol in w is going to be the same
as ‘c’; store this symbol in the state
• Read the rest of w
• On reading #, check that the symbol
immediately after is the one stored,
and that the input ends immediately
after that.
Non-Deterministic Finite Finite
Non-Deterministic Automata(NFA)
Automata(NFA)
Acceptance or Rejecting a String by a NFA machine M:
 For an NFA M = (Q, Σ, δ, q0, F) and string w ∈ Σ∗ , we say M accepts w if and only if δ*(q0,w)
 q for some q ∈ F.
 δ*  Extended transition function

Acceptance or Rejecting a Language by a NFA machine M:

 The language accepted or recognized by NFA M over alphabet Σ is L(M) = {w ∈ Σ∗ | M
accepts w}. A language L is said to be accepted/recognized by M if L = L(M).
Non-Deterministic Finite Finite
Non-Deterministic Automata(NFA)
Automata(NFA)
Summary:
• A Nondeterministic Finite Automaton (NFA) can have zero, one, or multiple transitions
corresponding to a particular symbol.
• It is defined to accept the input if there exists some choice of transitions that cause the
machine to end up in an accept state.
• Nondeterminism can also be viewed as a tree, or as a “guess-and-verify” concept.
• You can also have ε-transitions, where the NFA can change state without consuming an input
symbol.
Equivalence of DFA and NFA
• NFA is easier to construct than a DFA.
• DFA has as many states as NFA but DFA has a greater number of transitions.
• Worst case: For same language if NFA is having ‘n’ states, the DFA can have 2n states.
• Every DFA is a special case of an NFA where each state has exactly one transition for every
input symbol. Therefore, if L is accepted by a DFA, it is accepted by a corresponding NFA.

• How to prove DFA can do whatever NFA is doing? Or How to construct a DFA from an
NFA?
• Observation: the transition function of an NFA maps to subsets of states
• Idea: Make one DFA state for every possible subset of the NFA states
• By Subset Construction, because it involves constructing all subsets of the set of states of the
NFA.
Equivalence of DFA and NFA
• Given a NFA N= (QN , Σ, δN, q0, FN), then DFA D= (QD , Σ, δD, q, FD) such that
L(D) = L(N), input alphabets of the two automaton are same and start state of D is the set
containing only the start state of N.
• QD = P(QN), P(QN) denotes the power set of QN
• The start state of D, q= {q0}, so D has same start as N
• The set FD of accept states is equal to the set of all elements R of QD having the property
that R contains at least one accept state of N, i.e.,
FD = {R∈ QD : R ∩ F ≠ø}
• The transition function δD : QD X Σ  QD i.e for each set S in QD, for each input symbol
a in Σ,
δD (S, a) = ⋃(q in S)δN(q,a)
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:
Given a transition table/ transition diagram of NFA and using subset construction
generate the DFA.

L= All strings ends with 10

• NFA Tuples:
N= (QN , Σ, δN, q0, FN) = ({q0,q1,q2}, {0,1}, δ, q0, {q2})
Power set of NFA states QN
• The NFA has 3 states, power set will contain 23 = 8 states.
• Omitting the φ empty set there will be 23 - 1 = 7 states.
• If QN is set of states of NFA the P(QN) is the power set of QN, are possible states of the
DFA QD.
• Each of the sets in the power set represents a state in the DFA.
• QN ={q0,q1,q2}, P(QN)= QD = {φ, {q0}, {q1}, {q2}, {q0,q1}, {q0,q2}, {q1,q2}, {q0,q1,q2}}
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:
Subset Construction: The NFA can be converted to DFA using complete subset
construction or by lazy evaluation of states.
δD (S, a) = ⋃(q in S)δN(q,a)
S 0 1 Remarks δD(S, a) = ⋃(q in S)δN(q,a)

S is from P(QN)= QD = {φ, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}}
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:
S 0 1 Remarks δD(S, a) = ⋃(q in S)δN(q,a)
{q0} {q0} {q0,q1} δD({q0}, 0) = δN(q0) = {q0}
δD({q0}, 1) = δN(q0,1) ={q0,q1}
{q1} {q2} φ δD({q1}, 0) = {q2} δD({q1}, 1) = φ
{q2} φ φ δD({q2}, 0) = φ δD({q2}, 1) = φ
{q0,q1} {q0,q2} {q0,q1} δD({q0,q1}, 0) = δN(q0,0) U δN(q1,0)
= {q0} U {q2} = {q0,q2}
δD({q0,q1},1) = δN(q0,1) U δN(q1,1)
= {q0,q1} U φ = {q0,q1}
{q0,q2} {q0} {q0,q1} δD({q0,q2}, 0) = δ q0, 0 U δ q2, 0 = {q0} U φ = {q0}
δD({q0,q2}, 1) = δ q0, 1 U δ q2, 1 = {q0,q1} U φ ={q0,q1}
{q1,q2} {q2} φ δD({q1,q2}, 0) = δ q1, 0 U δ q2, 0 = {q2} U φ = {q2}
δD({q1,q2},1) = δ q1, 1 U δ q2, 1 = φ U φ = φ
{q0,q1,q2} {q0,q2} {q0,q1} δD({q0,q1,q2}, 0) = δ q0, 0 U δ q1, 0 U δ q2, 0
= {q0} U {q2} U φ = {q0,q2}
δD({q0,q1,q2},1) = δ q0, 1 U δ q1, 1 U δ q2, 1
= {q0,q1} U φ U φ = {q0,q1}
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:
S 0 1 Remarks δD (S, a) = ⋃(q in S)δN(q,a)
φ φ φ -
{q0} {q0} {q0,q1} δD({q0}, 0) = δN(q0,0) = {q0}
δD({q0}, 1) = δN(q0,1) ={q0,q1}
{q1} {q2} φ δD({q1}, 0) = {q2} δD({q1}, 1) = φ
*{q2} φ φ δD({q2}, 0) = φ δD({q2}, 1) = φ
{q0,q1} {q0,q2} {q0,q1} δD({q0,q1}, 0) = δN(q0,0) U δN(q1,0)
= {q0} U {q2} = {q0,q2}
δD({q0,q1},1) = δN(q0,1) U δN(q1,1)
= {q0,q1} U φ = {q0,q1}
*{q0,q2} {q0} {q0,q1} δD({q0,q2}, 0) = δ q0, 0 U δ q2, 0 = {q0} U φ = {q0}
δD({q0,q2}, 1) = δ q0, 1 U δ q2, 1 = {q0,q1} U φ ={q0,q1}
*{q1,q2} {q2} φ δD({q1,q2}, 0) = δ q1, 0 U δ q2, 0 = {q2} U φ = {q2}
δD({q1,q2},1) = δ q1, 1 U δ q2, 1 = φ U φ = φ
*{q0,q1,q2} {q0,q2} {q0,q1} δD({q0,q1,q2}, 0) = δ q0, 0 U δ q1, 0 U δ q2, 0
= {q0} U {q2} U φ = {q0,q2}
δD({q0,q1,q2},1) = δ q0, 1 U δ q1, 1 U δ q2, 1
= {q0,q1} U φ U φ = {q0,q1}
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:
Renaming the states:
•To make things simpler, rename the states from A to H.
A = φ, B={q0}, C={q1}, D={q2},
E={q0,q1}, F={q0,q2} G={q1,q2}, H= {q0,q1,q2}
State Name 0 1
A A A
B B E
C D A
*D A A
E F E
*F B E
,
*G D A
*H F E
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:

Reachable States: Identify the reachable states of QD

• The state itself is reachable.
• Start at B (initial state), the states in corresponding row B, E are reachable from
B, here new state found is E.
• Now goto State E, the states in corresponding row F, E are reachable from E, here
new state found is F.
• Now goto State F, the states in corresponding row B, E are reachable from F, here
no new state is found.
• So, the reachable states are B,E, and F and the remaining states A, C, D, G,H
are not reachable.
 CONVERTING
CONVERTING NFA TO
NFA TO DFA BY DFA BY COMPLETE
COMPLETE SUBSET CONSTRUCTION:
SUBSET CONSTRUCTION:
Construct DFA:
From the transition table, remove the entries of not reachable states.
State Name 0 1 State Name 0 1
A A A B B E
B B E E F E
C D A *F B E
*D A A Transition Table after removing
E F E non reachable states
*F B E
*G D A
*H F E 0 1
Transition Table before removing non reachable states
1 E 0 F
Conclusion: B 1
1. Given NFA  an equivalent DFA
2. [Link] states are same in this case. 0
3. [Link] transitions are more in DFA (6), than in NFA (4) Transition Diagram
CONVERTING NFA TO DFA BY COMPLETE SUBSET CONSTRUCTION:
• The transition table for the DFA is calculated. Although not all the 2N states will
be there. First thing to do is wherever there is the final state of the NFA mark
that with star (*) and q0 will also be start state for the DFA.

Short Cut Method

• The table can be filled using shortcut by first copying the NFA table for the first
four states since they are same as the NFA.
• Next for each element in the set for a copy from its corresponding row and union
all the sets.
 CONVERTING
CONVERTING NFA BY
NFA TO DFA TO LAZY
DFA BYEVALUATION
SUBSET / SUBSET
CONSTRUCTION:
CONSTRUCTION:
Lazy Evaluation / Subset Construction:
• The above method is very slow and time consuming. Since all 2N are not reachable
for every DFA so this method will speed up the process by avoiding extra work.
• Simple Idea: Start with the start state and only construct the states they are reachable
from starting state and similarly follow those states.
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET
CONSTRUCTION:
Given a transition table/ transition diagram of NFA and using subset construction generate the DFA.

L= All strings ends with 10

 NFA Tuples: N= ({q0,q1,q2}, {0,1},δ, q0, {q2})

S 0 1 Remarks δD (S, a) = ⋃(q in S)δN(q,a)
φ φ φ -
{q0} {q0} {q0,q1} δD ({q0}, 0) = δN(q0,0) = {q0}
δD ({q0}, 1) = δN (q0,1) ={q0,q1} //New State
{q0,q1} {q0,q2} {q0,q1} δD ({q0,q1}, 0) = δN (q0,0) UδN (q1,0)
= {q0} U {q2} = {q0,q2} //New State
δD ({q0,q1},1) = δN (q0,1) UδN (q1,1)
= {q0,q1} U φ = {q0,q1}
*{q0,q2} {q0} {q0,q1} δD ({q0,q2}, 0) = δ q0, 0 U δ q2, 0 ={q0}Uφ={q0}
δD ({q0,q2},1)=δ q0,1 Uδ q2, 1 ={q0,q1}Uφ={q0,q1}
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET
CONSTRUCTION:
 To make things simpler, rename the states from A to C.
 A = {q0}, B={q0,q1}, C={q0,q2}
Transition Table after renaming the states
State Name 0 1
A A B
B C B
*C A B

Transition Diagram
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:
Given a transition table of NFA, using subset construction generate the DFA.

Transition Diagram:
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:
Power set of NFA states QN
• The NFA has 4 states, power set will contain 24 = 16 states
• Omitting the φ empty set there will be 24 -1 = 15 states.
• If QN is set of states of NFA the P(QN) is the power set of QN, are possible states
of the DFA QD.
• Each of the sets in the power set represents a state in the DFA.
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:
Subset Construction:
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:
Subset Construction: Renaming the states:
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:

Reachable states:

Reachable states: 1, 5, 6, 7, 11, 12, 13,

15
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:

DFA:
CONVERTING NFA TO DFA BY LAZY EVALUATION / SUBSET CONSTRUCTION:

Convert the following NFAs to DFA.

1. 3.

2.
Finite automata with epsilon(ε) transitions
Extend the class of NFAs by allowing instantaneous (ε) transitions:
• The automaton may be allowed to change its state without reading the input
symbol.
• In automata, such transitions are depicted by labeling the appropriate arcs
with epsilon (ε).
Finite automata with epsilon transitions
Definition: A ε-NFA is a 5-tuple (quintuple) M=(Q,Σ,δ,q0,F) where
• Q is a set of states
• Σ is the alphabet of input symbols
• q0 ∈ Q is the initial state
• F ⊆ Q is the set of final states
• δ: Q × Σε → P(Q) is the transition function
Σε is defined to be (Σ ∪ ε)
• Note: ε is never a member of Σ
• ε-NFAs add a convenient feature but (in a sense) they bring us nothing new:
they do not extend the class of languages that can be represented.
• Both NFAs and ε-NFAs recognize the same languages.
Finite automata with epsilon transitions

δ:
0 1 ε
q0 {q0} {} {q1}
q1 {q1, q2} {q0, q3} {q2}
q2 {q2} {q2} {}
q3 {} {} {}

Finite automata Transition Table

Finite automata with epsilon transitions
• A string w = w1w2…wn is processed as
w = ε*w1ε*w2ε* … ε*wnε*
• Example: all computations on 00:
0 ε 0
q0 q0 q1 q2

• Let M = (Q, Σ, δ,q0,F) be an NFA-ε, then

• A String w in Σ* is accepted by M iff there exists a path in M from q0 to a
state in F labeled by w and zero or more ε transitions.
• The language accepted by M is the set of all strings from Σ* that are
accepted by M.
Epsilon-Closures : ε-closure() or ECLOSE():
• The set of all states that can be reachable from ‘q’ by zero or more ε
transitions (arcs labeled ε ).
• ε-closure(q) = {q}
ε-closure(q0) = ECLOSE(q0) = {q0, q1, q2}
ε-closure(q1) = ECLOSE(q1) = {q1, q2}
ε-closure(q2) = ECLOSE(q2) = {q2}
ε-closure(q3) = ECLOSE(q3) = {q3}

ε-closure(q) can be extended to sets of states by defining:

ε-closure(P) = ⋃qεQ ε-closure(q)
ε-closure({q1, q2}) = ε-closure(q1) ⋃ ε-closure(q2) = {q1, q2}
ε-closure({q0, q3}) = ε-closure(q0) ⋃ ε-closure(q3) = {q0, q1, q2, q3}
Extended Transitions and Languages for ε-NFA
Extended Transition function is defined as δ^ or δ* to reflect what happens on a sequence of
inputs, and it is defines as
• δ^ (q, ε) = ε-closure(q)
• δ^(q,w) = ε-closure(δ(δ^(R,x), a)) for any w in Σ*, w = xa in the form, a in Σ, and subset R
of Q.
Two Step process:
1. Compute the transitions on input a, for the subset R
2. Apply ε-closure to the members of the set computed in first step.
Extended Transitions and Languages for ε-NFA
δ^(q0, ε ) = ε-closure(q0) = {q0, q1, q2}
Let w=0  w= ε0  x= ε, a= 0 What is the difference between δ(q0, 0) and δ^(q0, 0)?
δ^({q0}, 0) = ε-closure(δ(δ^({q0}, ε), 0)) • δ(q0, 0) - Processes 0 as a single symbol, without ε
= ε-closure(δ({q0, q1, q2},0)) transitions.
= ε-closure(δ(q0, 0) U δ(q1, 0) U δ(q2, 0)) • δ^(q0, 0)- Processes 0 using as many as ε
= ε-closure({q0} U {q1, q2} U {q2}) transitions that are possible.
= ε-closure({q0, q1, q2})
= ε-closure({q0}) U ε-closure({q1}) U ε-closure({q2})
= {q0, q1, q2} U {q1, q2} U {q2}
= {q0, q1, q2}
δ^ ({q0}, 01) = ε-closure(δ(δ^ ({q0}, 0), 1))
= ε-closure(δ({q0, q1, q2}), 1)
= ε-closure(δ(q0, 1) U δ(q1, 1) U δ(q2, 1))
= ε-closure({ } U {q0, q3} U {q2})
= ε-closure({q0, q2, q3})
= ε-closure({q0}) U ε-closure({q2}) U ε-closure({q3})
= {q0, q1, q2} U {q2} U {q3}
= {q0, q1, q2, q3}
ε-NFA to NFA construction
Problem Statement: Given ε-NFA, constructing equivalent NFA without ε
transitions. (i.e. eliminating ε transitions).

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

Transition Table of N with ECLOSE()

q 0 1 ε ECLOSE(q)
q0 q0 - q1 {q0, q1, q2}
q1 {q1,q2} {q0,q3} q2 {q1, q2}
q2 q2 q2 - {q2}
q3 - - - {q3}
ε-NFA to NFA construction
Q 0 1 Summary
q0 {q0,q1,q2} {q0,q1,q2,q3} ECLOSE(δ(δ^({q0}, ε), 0))
ECLOSE(δ({q0, q1, q2},0) )
ECLOSE({q0,q1,q2}) {q0,q1,q2}
ECLOSE(δ(δ^({q0}, ε), 1))
ECLOSE(δ({q0, q1, q2},1))  ECLOSE({q0,q2,q3}){q0,q1,q2,q3}
q1 {q1,q2} {q0,q1,q2,q3} ECLOSE(δ(δ^({q1}, ε), 0))
ECLOSE(δ ({q1, q2},0))
 ECLOSE({q1,q2}) {q1,q2}
ECLOSE(δ(δ^({q1}, ε), 1))
ECLOSE(δ({q1,q2},1))
 ECLOSE{q0,q2,q3} {q0,q1,q2,q3}
q2 {q2} {q2} ECLOSE(δ(δ^({q2}, ε), 0))
ECLOSE(δ({q2},0)) ECLOSE({q2}) {q2}
ECLOSE(δ(δ^({q2}, ε), 1))
ECLOSE(δ({q2},1)) ECLOSE({q2}){q2}
q3 - - ECLOSE(δ(δ^({q3}, ε), 0)) ECLOSE (δ({q3},0)) -
ECLOSE(δ(δ^({q3}, ε), 1)) ECLOSE(δ ({q3},1))-
Transition Table of NFA N’ with δ operation on ECLOSE(q)
ε-NFA to NFA construction
• Same state set as N
• q0 is the starting state
• Let N = (Q, Σ, δ,q0,F) be an NFA-ε then an NFA N’ = (Q, Σ, δ’, q0,F’) as:
• F’ = F U {q} if ε-closure(q) contains at least one state from F, F’ = F otherwise
• q0 becomes a final state, since ECLOSE(q0) = {q0, q1, q2}; {q2} is final state of
N. Similarly, q1

NFA N’ for equivalent NFA N

ε-NFA to NFA construction
Problem: Eliminate ε transitions, and find NFA

NFA
ε-NFA to NFA construction
Problem: Eliminate ε transitions, and find NFA
ε-NFA to NFA construction
Problem Statement: Given ε-NFA, construct an equivalent NFA without ε
transitions. (i.e. eliminating ε transitions).
•Every NFA is an NFA-ε.
Given an ε-NFA N, this construction produces an NFA N' such that L(N')=L(N).
Let N = (Q, Σ, δ,q0,F) be an NFA-ε then an NFA N’ = (Q, Σ, δ’, q0,F’) as:
F’ = F U {q} if ε-closure(q) contains at least one state from F, F’ = F otherwise
δ’(q, a) = δ^(q, a) - for all q in Q and a in Σ
• δ’: (Q x Σ)  2Q is a function
• N’ has the same state set, the same alphabet, and the same start state as N and N’
has no ε transitions.
Parameter NFA to DFA ε-NFA to NFA
Input NFA N= (QN ,Σ,δN,q0,FN) NFA-ε N = (Q,Σ,δ,q0,F)
Output DFA D= (QD,Σ,δD,q0,FD) NFA N’ = (Q, Σ,δ’,q0,F’)
QD = P(QN) F’ = F U {q} if ε-closure(q) contains at
P(QN) denotes the power set of QN least one state from F,
FD = {R∈ QD : R ∩ F ≠ø} F’ = F otherwise
δD : QD X Σ  QD δ’: (Q x Σ)  P(Q)
δ’(q,a)=δ^(q,a) for all q in Q and a in Σ
Transition δD(S,a)=⋃(q in S)δN(q,a) δ^(q,a) = E-Close (δ(δ^({q}, ε), a))
Function δ’(q, ε)= E-Close(q)
ε-NFA to DFA construction
ε-NFA NFA DFA

Time Consuming Process

ε-NFA DFA
ε-NFA to DFA construction
Steps:
For each state in N identify ECLOSE(q)
q a b ε ECLOSE(q)
0 {1,2} - {3} {0,1,3}
ε-NFA denoted by N
1 - {3} - {1}
2 - - {3} {1,2,3}
*3 - - {1} {1,3}
ε-NFA to DFA construction
Identify transitions
Step 1: Start with ECLOSE(0) where 0 is start state Let it be q0D or S0
Step 2: δD (S0, a)  ECLOSE ⋃(q in S)δ(q,a) for every a in Σ
Identify transitions i.e. sets until no more new set / state is found.
Step 3: Identify final state(s), F’⊆ QD, All subsets of states of ε-NFA that contain an accepting
state of the ε-NFA.
ECLOSE(0) = {0,1,3}  Let it be S0
δD (S0, a)  ECLOSE (δ(0, a) U δ(1,a) U δ(2,a))
ECLOSE({1,2} U ø U ø)
ECLOSE({1,2})
ECLOSE(1) U ECLOSE(2)
{1} U {1,2,3}
{1,2,3}  New State, let it be S1
 ε-NFA to DFA construction
q a b
δD (S0, b)  ECLOSE (δ(0,b) U δ(1,b) U δ(2,b))
*S0 S1 S2
ECLOSE( ø U {3} U ø) ECLOSE({3})
{1,3} New State, let it be S2
*S1 - S2
δD (S1, a)  ECLOSE (δ(1, a) U δ(2,a) U δ(3,a))
*S2 - S2
ECLOSE(ø U ø U ø)  ECLOSE(ø)  Ø
δD (S1, b)  ECLOSE (δ(1, b) U δ(2,b) U δ(3,b)) 3 is the final state in N,
ECLOSE( {3} U ø U ø)  ECLOSE({3}) S0, S1and S2 contains 3 in the sets.
{1,3} S2
δD (S2, a)  ECLOSE (δ(1, a) U δ(3,a))
ECLOSE(ø U ø)  ECLOSE(ø) Ø
δD (S2, b)  ECLOSE (δ(1, b) U δ(3,b))
ECLOSE( {3} U ø )  ECLOSE({3})
{1,3} S2 DFA
No more new states
ε-NFA to DFA construction


a
2 3
 
start
0

1 6

7
a 8
b 9
b 10

 
b
4 5

q a b ε ECLOSE(q)
0 - - {1,7} {0,1,7,2,4}  {0,1,2,4,7}
1 - - {2,4} {1,2,4}
2 3 - - {2}
3 - - {6} {3,6,1,7,2,4}  {1,2,3,4,6,7}
4 - 5 - {4}
5 - - {6} {5,6,1,7,2,4}  {1,2,4,5,6,7}
6 - - {1,7} {6,1,7,2,4}  {1,2,4,6,7}
7 8 - - {7}
8 - 9 - {8}
9 - 10 - {9}
*10 - - - {10}
ε-NFA to DFA construction
-closure({0}) = {0,1,2,4,7} = S0
δD (S0, a) =-closure(δ({0,1,2,4,7},a))=-closure( {3, 8} )={1,2,3,4,6,7,8}= S1
δD (S0, b) = -closure(δ({0,1,2,4,7},b))=-closure( {5} )={1,2,4,5,6,7}= S2
δD (S1, a) = -closure(δ({1,2,3,4,6,7,8},a) =-closure( {3, 8} )= S1
δD (S1, b) = -closure(δ({1,2,3,4,6,7,8},b) =-closure( {5, 9} )={1,2,4,5,6,7,9}= S3
δD (S2, a) = -closure(δ({1,2,4,5,6,7},a))=-closure( {3,8} )= S1
δD (S2, b) = -closure(δ({1,2,4,5,6,7},b))=-closure( {5} )= S2
δD (S3, a) = -closure(δ({1,2,4,5,6,7,9},a))=-closure( {3,8} )= S1
δD (S3, b) = -closure(δ({1,2,4,5,6,7,9},b))=-closure( {5,10} )={1,2,4,5,6,7,10}= S4
δD (S4, a) = -closure(δ({1,2,4,5,6,7,10},a))=-closure( {3,8} )= S1
δD (S4, b) = -closure(δ({1,2,4,5,6,7,10},b))=-closure( {5} )= S2

State a b b
S2
S0 S1 S2 b b
S1 S1 S3 a
a

S2 S1 S2 S0 a S1
b
S3
b
S4
S3 S1 S4 a

*S4 S1 S2 DFA for equivalent ε-NFA

ε-NFA to DFA construction
Problem Statement: Given ε-NFA N, constructing equivalent DFA D without ε transitions.
(i.e. eliminating ε transitions), such that L(N) = L(D)

Let N = (Q, Σ, δ,q0,F) be an NFA-ε then define an DFA D = (QD, Σ, δD,q0D,F’) as:
• QD  P(Q) powerset of Q
• Σ  Same alphabet
• δD : QD X Σ  QD
• q0D  initial state of D, obtained by ECLOSE (q0) where q0 is initial state in ε-NFA.
The initial state of the DFA is the ε-closure of the initial state of the Epsilon NFA.
[Which is different from normal NFA]
• F’  Set of final states. F’⊆ QD, All subsets of states of ε-NFA that contain an
accepting state of the ε-NFA.
Parameter NFA to DFA ε-NFA to NFA ε-NFA to DFA

Input NFA N= (QN ,Σ,δN,q0,FN) NFA-ε N = (Q,Σ,δ,q0,F) NFA-ε N = (Q,Σ,δ,q0,F)

Output DFA D= (QD,Σ,δD,q0,FD) NFA N’ = (Q, Σ,δ’,q0,F’) DFA D = (QD, Σ, δD,q0D,F’)
QD = P(QN) F’ = F U {q} if ε-closure(q) QD = P(QN)
P(QN) denotes the power set of contains at least one state from δD : QD X Σ  QD
QN F, F’ = F otherwise q0D  initial state of D, obtained
FD = {R∈ QD : R ∩ F ≠ø} δ’: (Q x Σ)  P(Q) by ECLOSE (q0) where q0 is
δD : QD X Σ  QD δ’(q,a)=δ^(q,a) initial state in ε-NFA.
for all q in Q and a in Σ F’  Set of final states. F’⊆ QD,
All subsets of states of ε-NFA
that contain an accepting state of
the ε-NFA.
Transition δD(S,a)=⋃(q in S)δN(q,a) δ^(q,a) = E-Close (δ(δ^({q}, ε), Start with ECLOSE(0) where 0
Function a)) is start state.
δ’(q, ε)= E-Close(q) Let ECLOSE(0) = S0
δD (S0, a)  ECLOSE ⋃(q in
S)δ(q,a)
Identify transitions until no more
new set is found.
Problems: ε-NFA to DFA construction

1. Convert the following ɛ-NFA to DFA

2. Convert the following ɛ-NFA to DFA

Problems: ε-NFA to DFA construction

3. Convert the following ɛ-NFA to DFA

4. Convert the following ɛ-NFA to DFA

The top half of the NFA is the x = 0 mod 3 machine. The bottom half of the NFA is a x = 0 mod 4 machine.
The NFA is the union of these two machines. Therefore L(M)= binary strings x such that x = 0 mod 3 or x = 0 mod 4.