THEORY OF COMPUTATION - BCS503

MODULE - 1 NOTES
Contents

1 Introduction Finite State Automaton 2

1.1​ Why do we need to study this subject? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1​ Introduction to Finite Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2​ Structural Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3​ Automata and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2​ Central Concept of Automata Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1​ Alphabets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2​ Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3​ Functions on string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4​ Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.5​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3​ Deterministic Finite Automata (DFA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1​ Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2​ Notations of Deterministic Finite State Automata . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.3​ How DFSA Processes? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.4​ Extended Transition Function (δˆ) to DFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.5​ Language of DFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.6​ Examples of DFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.7​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.3.8​ Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.4​ Non-Deterministic Finite Automata (NFA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.4.1​ Formal view and Definition of NFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.4.2​ Extended Transition Function δˆ to NDFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.4.3​ Language of an NDFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.4.4​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.4.5​ Examples of NDFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.4.6​ Equivalence Deterministic and Non-Deterministic Finite State Automata (NFSA) . . . . . . 43
1.4.7​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.4.8​ Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.5​ Applications of Theory of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.5.1​ An Application: Text Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.5.2​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.6​ Non-deterministic Finite Automata with ϵ Transition (ϵ- NFA) . . . . . . . . . . . . . . . . . . . . . 54
1.6.1​ Definition and uses of ϵ - Transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.6.2​ Definition of ϵ- NFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.6.3​ Formal Notation of an ϵ- NDFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.6.4​ Epsilon-Closures (ϵ - closure or ecl()) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.6.5​ Extended Transition Function to ϵ- NDFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.6.6​ Language of ϵ- NDFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.6.7​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.6.8​ Equivalent ϵ- NDFSA and DFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.6.9​ Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
 MODULE 1

INTRODUCTION FINITE STATE AUTOMATON

1.1​ Why do we need to Finite Automata?

Finite automata are a useful model for designing many hardware and software which helps in the
computational domain.

1.1.1​ Introduction to Finite Automata

Finite automata are useful computing models for many important kinds of hardware and software based
design and applications.
Finite automata is used in
•​ Designing software which helps in checking the behavior of digital circuits and scanning large
bodies of text in the web pages to find the occurrences of words.
•​ Lexical analyzer is one of the phases in a typical compiler, that breaks the input into logical units
or tokens, such as identifiers, keywords etc.
•​ Artificial Intelligence to predict the occurrence of an event.
•​ Software for scanning large bodies of texts such as collections of Web pages to find the
occurrences of words, phrases, or other patterns.
•​ Software for verifying systems of all types that have a finite number of distinct states such as
communications protocols or protocols for secure exchange of information
Finite Automaton is an abstract computing device which receives the sequence inputs and gives the
desired output. The output will be either accept or reject.
Finite automata have the finite number of states used to remember the bit information of a machine.
Finite automaton will have limited memory space of 1 bit. Hence it cannot remember the previous
processed input.
Example 1: Consider the switch of TV or Computer or any electronic device will have only two states
(on, off ).
Initially the devices will be in off state and if you push the button, it goes to on state from off state
where push input symbol is accepted. If you push the button again it goes to off state from on state and
input is accepted as shown in figure.

Push
Figure 1.1: Generic Model of Finite Automata for electronic device
Example 2: Recognition of a word “then”

Figure 1.2: Finite automata model for recognition of word “then”

The lexical analyzer examines one character of the program that it is compiling at a time and the next character
to be examined is the input to the automaton
The start state corresponds to the empty string.
Each state has a transition on the next letter of then to the state that corresponds to the next larger prefix.
It is the job of this automaton to recognize when then has been seen.
If the lexical analyzer accepts the word, it is considered that state will be accepting state

Pictorial representation of Finite Automaton

Start state: the state in which the system is placed initially.
Start state will be indicated by the word Start within a circle and an arrow leading to that state
One or more states can be final or accepting states. Entering one of these states after a sequence of inputs
indicates that the input sequence is good in some way.
Accepting state will be represented by a double circle.

1.1.2​ Structural Representation

Two notations used in study and applications of automata are:
1.​Grammars:
Grammars are useful models when designing software that processes data with a recursive
structure The best example is a parser the component of a compiler that deals with the recursively
nested features of the typical programming language such as expressions: arithmetic, conditional
and so on.
For example a grammatical rule
E⇒ E+ E
states that an expression can be formed by taking any two expressions and connecting them by a
plus sign.
This rule is typical of how expressions of real programming languages are formed.

2.​Regular Expressions:
Regular expression denotes the structure of data and the patterns of strings.
For example: Consider regular expression
[A − Z][a − z]*[ ][A − Z][A − Z]
represents capitalized words followed by a space and two capital letters.
 This expression can recognize Ithaca NY, Xyz AB, …
In regular expression
[A-Z] represents a range of characters from capital A to capital Z (i.e., any capital letter)
[ ] is used to represent the blank character
* symbol represents any number of the preceding expression

The above regular expression cannot recognize the pattern two capitalized words.
For example it cannot recognize
Palo Alto CA
Xyz Pqr AB

[A-Z][a-z]*([ ][ A-Z][a-z]*)*[A-Z][A-Z] -recognizes multiple capitalized words followed by two

capital letters

Parentheses are used to group components of the expression

1.1.3​ Automata and Complexity

The automata are the essential tool for studying the limits of any computing models. The complexity or
limitations of any computation is resides in the following categories:
•​ What can a computer do at all? This study is called ”Decidability” and the problems that can be
solved by computer are called ”Decidable”.
If algorithm exists to solve a problem-decidable, otherwise undecidable
•​ What can a computer do efficiently? This study is called ”Intractability” and the problems that can
be solved by a computer using no more time than some slowly growing function (polynomial
functions) of the size of the input are called ”Tractable”. If a problem cannot be solved in
polynomial time the problem is called Intractable.

Review Questions
1.​Why do we need to study finite automata?
2.​What is Automata?
3.​Which are the two structural representations of Finite Automata.
4.​What is decidability?
5.​What is Intractability?
1.2​ Central Concept of Automata Theory
This section discusses terms used in designing finite state automata. The terms include
alphabet: a set of symbols
strings: a list of symbols from an alphabet
language: a set of strings from the same alphabet

1.2.1​ Alphabets
Alphabets are the finite, non-empty set of symbols and is denoted by Σ.
Common alphabets are:
Σ={0,1} binary alphabet
Σ={a,b,...z} set of all lower​ case letters
Set of all ASCII characters or the set of all printable ASCII characters

1.2.2​ Strings
A string (or word) is a finite sequence of symbols chosen from some alphabet
For example 01101 is a string from the binary alphabet Σ={0,1}
The string 111 is another string chosen from this alphabet

Empty String: Empty string is a string with zero occurrences of symbols and is denoted by ϵ.
ϵ represents the empty string.

Length of String: Length of string is the number of positions for symbols in the string.
Length of a string is the number of symbols in the string.
String W = 0010, then length of string |W | = |0010| = 4
|ϵ| = 0

Powers of an Alphabet
If Σ is an alphabet, we can express the set of all strings of a certain length from that alphabet by using an
exponential notation
Σk the set of strings of length k, whose symbols are in Σ
The set of all strings over an alphabet is conventionally denoted Σ*
{0,1}*={ϵ,0,1,00,01,10,11,000,...}
The set of nonempty strings from alphabet is denoted Σ+
Concatenation of String:
If X and Y are two given strings, then concatenation of these strings can be defined as W = X.Y
The length of concatenated string is |W | = |X.Y | = |X| + |Y |
Let x and y be strings, xy denotes the concatenation of x and y, that is the string formed by making a copy
of x and following it by a copy of y.
If x is the string composed of i symbols x a1a2.... ai and y is the string composed of j symbols y
b1b2...bj then xy is the string of length i+j.
xy= a1a2..aib1b2…b

Example: Let x=01101, y=110

xy=01101110
ϵw=wϵ=w, ϵ:identity for concatenation

Replication of String: For each string W and each natural numbers i, the string Wi is is replication of
string and it is defined as
W0=ϵ
Wi+1 = WiW
Reverse of string: The process of writing the string from the last symbol of the main string is called
reverse of string. If string W is given, then reverse of string is denoted as WR

Concatenation and Reverse of string: If the given two string X, Y and the concatenation of these two
strings are defined as W = X.Y and the reverse of the string W is as follows:
WR = (XY )R
WR = Y RXR

Relations on string
Prefix string: is any number of leading symbols in the strings

Example If the string W = xyz, then

string W has prefix
ϵ(empty string), x, xy and xyz.

Consider string Raja, the various prefixes are

ϵ, R, Ra, Raj and Raja.

Suffix String: is any number of trailing symbols in the strings.

Example if the string W = xyz.
The string W has Suffix ϵ(empty string), z, yz and xyz.

Consider string Raja, the various prefixes are

ϵ, a, ja, aja and Raja.

1.2.3​ Languages
A language is a collection or set of strings over the power of an alphabets, denoted by L.
Here L is the subset of Σ∗.
•​ A language is the set of strings consisting of equal number of 0’s and equal number of 1’s.

L = {ϵ, 01, 10, 0011, 0101, 1100, 010101, etc}

•​The language is a set of strings consisting of n number of 0’s followed n number of 1’s for n ≥ 0.

L = {ϵ, 01, 0011, 000111, 00001111​ etc}

•​Σ∗ is the Language over the input alphabet Σ.
•​ A language consisting of empty string is represented as {ϵ}
•​ ϕ represents the empty language.
•​ {ϵ} language consisting of empty string
•​ Φ is not equal to {ϵ}

Techniques for Defining the Languages

The language is a set of strings defined over the input alphabet.
The language can be constructed with the help of a grammar and the string must be in the language.
The languages are written in English sentences or in mathematical formulas.
{w| something about w}
Examples are
{w| w consists of an equal number of 0s and 1s}
{w| w is a binary integer that is prime}
{w| w is a syntactically correct C program}

There are many techniques to define the language for given problems as follows:
w can be expression with parameters and describe the strings in the language by stating conditions on
the parameters
L = {W |W ∈ Σ∗}
{0n1n| n≥1}, the set of 0 to the n, 1 to the n such that n is greater than or equal to 1.
This language consists of the strings {01, 0011, 000111,…}
{0i1j| 0≤i≤j } This language consists of strings with some 0s (possibly none) followed by at least as
many 1s.

Some of the examples and techniques for constructing the languages for a given problem is as follows:
Example The empty language is written as

L=ϕ

Example Define the language over Σ = {0, 1} which contains the string ”any number of 0’s precedes
any number of 1’s.

L = {0m1n|m, n ≥ 0}

Example Define the language over Σ ={0, 1} which accepts the string beginning with 0.

L = {0m1n|m>0, n ≥ 0}

Cardinality of Languages
The cardinality of language is defined as the number of strings in the given language.
The number of strings can be identified based on the length of language.
The smallest length language over is ϕ that is 0 and the largest language is infinite.

Functions on Languages
The various functions can be performed on the languages over Σ.
Since the language is a set and Σ it is a collection of strings, the set operations can be applied over the languages.
Given two language L1 and L2 over the the functions on these languages can be performed as follows:
L1 = { String with even number of 0’s } = {ϵ, 00, 0000, 000000,.......}
L2 = { String with both even and odd number of 0’s } = {ϵ, 0, 00, 000, 0000, ……}.

1.​Union: The Union of given two languages are denoted by L1 ∪ L2

L1 ∪ L2 = {ϵ, 0, 00, 000, 0000, 00000, 000000, ….}

2.​Intersection: The Intersection of given two languages are denoted by L1 ∩ L2

L1 ∩ L2 = {ϵ, 00, 0000, 000000,.......} = L1

3.​Difference: The difference between given two languages are denoted by L2 − L1

L2 − L1 = {ϵ, 0, 00, 000,​ } = L2

4.​Concatenation: The concatenation any given languages are as follows L1L2L3 = L1(L2L3) = (L1L2)L3
 5.​Concatenation and Reverse
Theorem 1 Given two language L1, L2 defined over Σ∗, prove that, (L1L2)R = LRLR
Proof. Given two languages over the input alphabet Σ
L1 = {x|x∈∑*}
L1
L2 = {y|y∈∑*}
L2
Concatenation of L1 and L2 is
L1.L2 ={x.y|x ∈∑*, 𝑦∈∑*}
L1 L2

(L1.L2)R={(x.y)R|x ∈∑*, 𝑦∈∑*}

L1 L2

(L1.L2)R={[Link]|x ∈∑*, 𝑦∈∑*}

L1 L2

(L1.L2)R={yR|y ∈∑*}.{xR|x ∈∑*}.

L2 L1

(L1.L2)R= L2R L1R

1.2.4​ Review Questions

1.​Define Alphabets
2.​What is Power of an Alphabet?
3.​What is String?
4.​What is language?
5.​What is the difference between Φ and {ϵ}
1.3​ Deterministic Finite Automata (DFA)
Consider electronic switch which has two states (on, off )
Consider off- initial state, one input symbol (push)
on, off-Acceptance state
The transition from one state to another state happens on input push.

Input: Push
Set of States: off, on
Initial State: off
Transitions: on to off
off to on
Acceptance State: on, off

1.3.1​ Definition
Definition: DFSA consist of 5-tuples
M = (Q, Σ, δ, q0, F )
•​ Q is the set of states.
•​ Σ is the set of input symbols (or alphabet).
•​δ is a transition function. δ : QX Σ→Q.
•​q0 ∈ Q is the initial state or start state of DFSA.
•​F ∈ Q is the set of final or accepting states of DFSA.

Example: Considering electronic switch,

Set of states, Q = {off, on}
Set of input symbols Σ = {push}
Transition function. δ : QX Σ→Q.
δ(CurrentState, InputAlphabet) = NextState
δ(off, push) = on
δ(on, push) = off
Initial state or start state of DFSA.

q0=off
Set of final states, F={on,off}

1.3.2​ Notations of Deterministic Finite State Automata

Transition function defines a set of paths from one state to another state.
Transition function can be depicted using a table or diagram.
Notations of DFSA are:
Transition table
Transition diagram

Transition Table:

Tabular representation of the transition function is called transition table.

Consider electronic switch

Transition function can be represented in terms of transition table as shown below:

δ Push
off on
→
on off

Transition Diagram:
Pictorial representation of the transition function is called a transition diagram or state transition
diagram.
The below picture depicts the transition diagram.

Write Finite automata to accept at least single “a” over the Σ = {a}

5-tuple of DFSA as shown below:

InputAlphabet Σ : {a}
Set of States Q: {q0, q1}
InitialState: q0
FinalState F: q1
TransitionFunction δ δ(q0, a) = q1
. δ(q1, a) = q1

Transition Table:
 δ a
→ q0 q1
q1 q1

Transition Diagram:

Exercise:
Write finite automata which accepts all the strings starting and ending with a over the alphabet {a, b}
Transition diagram

1.3.3​ How DFSA Processes?

How the input string is processed in the Deterministic Finite State Machine?
whether a string can fit into the DFSA or not by verifying the last symbol position on the state, if it
belongs to the final state, the string will be accepted otherwise rejected.

Example Consider finite automata which accepts at least one a

input string W = aaa.
The input string process is as shown below for the DFSA.
For the first input symbol a: δ(q0, a) = q1​
For the second input symbol a: δ(q1, a) = q1​
for the last input symbol a: δ(q1, a) = q1
q1 ∈ F final state, hence the input string is accepted.
1.3.4​ Extended Transition Function (δˆ) to DFSA
The extended transition function for DFSA decides whether the input string will be accepted or rejected
by scanning the entire input string.
It takes two arguments i.e current state q0 & input string W and produces the output as next state,
recursively.
If the next state, say p ∈ F , then the input string will be accepted, otherwise it will be rejected.

The extended transition function will be proved by the induction hypothesis method.

The input string will be divided into two parts i.e W = xα where x is the remaining input string and α is
the last input symbol of the string.
The remaining input string x will be divided into two parts i.e x = xα recursively until it x ∈ ϵ, that
means it reaches the base condition.
Basis: δˆ(q0, ϵ) = q0. The transition from the state q0 on with out any input alphabet or zero symbol or
NULL symbol i.e ϵ will be in the same state i.e q0.

Induction: The input string will be divided into two parts W = xα where x is the remaining input
string and α is the last input symbol of the string.
The remaining input string x will keep on dividing into two part x = xα recursively until x ∈ ϵ, that
means until it gets δˆ(q0, ϵ).

δˆ(q0, W ) = δˆ(q0, xα)

δˆ(q0, xα) = δ(δˆ(q0, x), α) Recursively

Example The input string W = aaa for the above example to process it, then the extended transition
function
δˆ can be written as shown below.

Basis: δˆ(q0, ϵ) = q0

Induction:
δˆ(q0, W ) = δˆ(q0, aaa) in the next step x=aa and α = a
δˆ(q0, aaa) = δ(δˆ(q0, aa), a) In the next step x=a and α
=a
δ(δˆ(q0, aa), a) = δ(δ(δˆ(q0, a), a), a) In the next step x=ϵ and α = a
δ(δ(δˆ(q0, a), a), a) = δ(δ(δ(δˆ(q0, ϵ), a), a), a)

Now this has reached to base case and start returning the next state of each transition function.
δ(δ(δ(δˆ(q0, ϵ), a), a), a) = δ(δ(δ(q0, a), a), a) - δˆ(q0, ϵ) has been replaced by q0 by the base case.
δ(δ(δ(q0, a), a), a) = δ(δ(q1, a), a) - δ(q0, a) has been replaced by q1 by transition diagram.
δ(δ(q1, a), a) = δ(q1, a) - δ(q1, a) has been replaced by q1 by transition diagram.
δ(q1, a) = q1 - δ(q1, a) has been replaced by q1 by transition diagram
and here there is no more input symbol & q1 ∈ F, hence the string is accepted.
1.3.5​ Language of DFSA
The Language of Deterministic Finite State automata D = (Q, Σ, δ, q0, F ) is denoted as L(D) and can be defined
as
L = {W | W ∈ Σ∗ s.t δˆ(q0, W ) ∈ F }
The language of DFSA D, is the set of string W over input alphabet Σ such that, the string should be processed
by using extended transition function and should be accepted.
1.3.6​ Examples of DFSA
We design DFSA for some of the given Regular Languages and verify whether the strings of language
are accepted by the DFSA or not by processing the input string.
The designing of DFSA can be categorized into following problems:
•​ Problems on Atleast and Atmost
•​ Problems on Starting and/or Ending
•​ Problems on Sub-string
•​ Problems on Even and/or Odd
•​ Problems on Consecutive
•​ Problems on precedes
•​ Problems on Divisible by k
•​ Problems on Modulo K-Counter
The following procedure/steps are used to design the deterministic finite state automata and can be
used to construct the all categories of DFSA above mentioned except Divisible by K-Problems and
Modulo K-Counter Problems.
•​Step 1: Identify the input alphabet Σ, minimum String (MS) required to design the DFSA and draw the
state transition diagram for the minimum string with initial State.
•​Step 2: Construct the rest of the transition function δ for each input symbol on each state except
transitions of the MS state transition diagram.
•​Step 3: Identify the final state by processing the input string and construct the final state transition
table & state transition diagram.
Example 13 Design a DFSA to accept the strings of a′s having atleast two a or Design the DFSA for the Language
L = {an | n ⩾ 2}.
Step 1: Input Alphabet Σ = {a}, MS = aa and three states are required to accept two a. The state
transition Diagram for Minimum String is as shown below:

start

Step 2: Constructing the remaining transition function δ for all input alphabet Σ on each state. That
means we need to verify whether transition on each state is valid or not by testing the valid input string
as shown below:

δ(q0, a) =
q1 δ(q1, a)
= q2 δ(q2,
a) =?
Here we need to find the transition for input alphabet a on
state q2. For the transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W = aaa will not be accepted even
though it is a valid string. Hence this transition δ(q2, a) = q0 is not valid.
•​ If the transition function is δ(q2, a) = q1, then the input string W = aaa will not be accepted even
though it is a valid string. Hence this transition δ(q2, a) = q1 is not valid.
•​ If the transition function is δ(q2, a) = q2, then the input string W = aaa and all other valid strings
will be accepted. Hence the remaining transition function is δ(q2, a) = q2.
Step 3: Constructing the Final state transition table and state transition diagram
Transition Table:

Transition Diagram:
a

start

Atleast problems
The same procedure need to be followed as we have seen in the previous example.
Example 14 Design a DFSN to accept the strings of a’s and b’s having atleast two b’s.
Step 1: Input Alphabet Σ = {a, b}, MS = bb and three states are required to accept bb. The state
transition Diagram for Minimum String is as shown below:

start
Step 2: Constructing the remaining transition function δ over the input alphabet Σ on each state. That
means we need to find whether transition on each state for each input symbol is valid or not by testing
the input string as shown below:
Here we have the transitions
δ(q0, b) = q1
δ(q1, b) = q2
And We need to identify the remaining transition Function as shown below
δ(q0, a) =?
δ(q1, a) =?
δ(q2, a) =?
δ(q2, b) =?
For The Transition δ(q0, a) =?
•​ If the transition function is δ(q0, a) = q1, then the input string W = ab will also be accepted even
though it is invalid string. Hence this transition δ(q0, a) = q1 is not valid.
 •​ If the transition function is δ(q0, a) = q2, then the input string W = a will also be accepted even
though it is invalid. Hence this transition δ(q0, a) = q2 is not valid.
•​ If the transition function δ(q0, a) = q0, then the input string W = abb will be accepted. Hence the
Transition Function δ(q0, a) = q0 is valid.
For The Transition δ(q1, a) =?
•​ If the transition function is δ(q1, a) = q0, then the input string W = bab will not be accepted even
though it is valid string. Hence this transition δ(q1, a) = q0 is not valid.
 •​ If the transition function is δ(q1, a) = q2, then the input string W = ba will also be accepted even
though it is invalid string. Hence this transition δ(q1, a) = q2 is not valid.
•​ If the transition function is δ(q1, a) = q1, then the Valid input string like W = aaabaab will be
accepted. Hence this Transition Function is δ(q1, a) = q1 is valid.
For The Transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W = bba will not be accepted even
though it is a valid string. Hence this transition δ(q2, a) = q0 is not valid.
•​ If the transition function is δ(q2, a) = q1, then the input string W = bba will not be accepted even
though it is a valid string. Hence this transition δ(q2, a) = q1 is not valid.
•​If the transition function is δ(q2, a) = q2, then the input string W = bba is a valid string & accepted,
because language can end with any number of a′s or b′s. Hence this Transition Function δ(q2, a) =
q2 is valid.
For The Transition δ(q2, b) =?
•​ If the transition function is δ(q2, b) = q0, then the input string W = bbb will not be accepted even
though it is a valid string. Hence this transition δ(q2, b) = q0 is not valid.
•​ If the transition function is δ(q2, b) = q1, then the input string W = bbb will not be accepted even
though it is a valid string. Hence this transition δ(q2, b) = q1 is not valid.
•​If the transition function is δ(q2, b) = q2, then the input string W = bbb is a valid string and other
valid strings will also be accepted because the language can end with any number of b′s. Hence
the Transition Function δ(q2, b) = q2 is valid.
Step 3: Constructing the Final state Transition Table and state Transition Diagram
Transition Table:

δ a b
→ q0 q0 q1
q1 q1 q2
q2
q2 q2

Transition Diagram: ​

Starting with problems

For this criteria also the same procedure needs to be followed as we have seen in the previous section example.

Example 15 Design a DFSN to accept the strings of a’s and b’s starting with ab or Design the DFSA to
accept the Language L = {abW | W ∈ (a + b)∗}
Step 1: Input Alphabet Σ = {a, b}, MS = ab and three states are required to accept ab. The state transition
Diagram for Minimum String is as given below:
 start
Step 2: Constructing the remaining transition function δ over the input alphabet Σ on each state. That
means we need to verify whether transition for each input symbol on each state is valid or not by
testing the input string as shown below:
Here we have the transitions
δ(q0, a) = q1
δ(q1, b) = q2
We need to identify the remaining transition Function as shown below
δ(q0, b) =?
δ(q1, a) =?
δ(q2, a) =?
δ(q2, b) =?
For The Transition δ(q0, b) =?
•​ If the transition function is δ(q0, b) = q0, then the input string W = bab will also be accepted even
though it is invalid which is starting with b. Hence this transition δ(q0, b) = q0 is not valid.
•​ If the transition function is δ(q0, b) = q1, then the input string W = bb will also be accepted even
though it is invalid string. Hence this transition δ(q0, b) = q1 is not valid.
•​ If the transition function is δ(q0, b) = q2, then the input string W = b will also be accepted even
though it is invalid string. Hence the Transition Function is δ(q0, b) = q2 is not valid.
•​ Hence the transition δ(q0, b) = Trap will move to the trap state. This transition will be optional
whether you can show it in terms of table or transition diagram.
For The Transition δ(q1, a) =?
•​ If the transition function is δ(q1, a) = q0, then the input string W = aaab will also be accepted even
though it is invalid string. Hence this transition δ(q1, a) = q0 is not valid.
•​ If the transition function is δ(q1, a) = q1, then the input string W = aab will also be accepted even
though it is invalid string. Hence this transition δ(q1, b) = q1 is not valid.
•​ If the transition function is δ(q1, a) = q2, then the input string W = aa will also be accepted even
though it is invalid string. Hence the remaining Transition Function is δ(q1, a) = q2 is not valid.
•​ Hence the transition δ(q1, a) = Trap will move to trap
state. For The Transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W = aba will not be accepted even
though it is a valid string which starts with ab. Hence this transition δ(q2, a) = q0 is not valid.
•​ If the transition function is δ(q2, a) = q1, then the input string W = aba will not be accepted even
though it is a valid string which is starting with ab. Hence this transition δ(q2, a) = q1 is not valid.
•​ If the transition function is δ(q2, a) = q2, then the input string W = aba & other valid strings will
also be accepted. Hence this Transition Function δ(q2, a) = q2 is valid.
For The Transition δ(q2, b) =?
•​ If the transition function is δ(q2, b) = q0, then the input string W = abb will not be accepted even
though it is a valid string which is starting with ab. Hence this transition δ(q2, b) = q1 is not valid.
 •​ If the transition function is δ(q2, b) = q1, then the input string W = abb will not be accepted even
though it is a valid string which is starting with ab. Hence this transition δ(q2, b) = q1 is not valid.
•​ If the transition function is δ(q2, b) = q2, then the input string W = abb & other valid strings will
also be accepted. Hence the Transition Function δ(q2, b) = q2 is valid
NOTE: For the transition δ(trap, a) =? and δ(trap, b) =? will be always on the same state itself i.e
δ(trap, a) = trap
δ(trap, b) = trap
Step 3: Constructing the Final Transition Table and Transition Diagram
Transition Table:
δ a b
→ q0 q1 trap
q1 trap q2
q2
q2 q2
Transition Diagram:
a,b

start

a,b

Ending with problems

Here also the same procedure need to be followed as we have seen in the previous section example.
Example 16 Design a DFSN to accept the strings of a’s and b’s Ending with ab or Design the DFSA to
accept the Language L = {Wab | W ∈ (a + b)∗}
Step 1: Input Alphabet Σ = {a, b}, MS = ab and three states are needed to accept ab. The state transition Diagram
for Minimum String is as shown below:

start
Step 2: Constructing the remaining transition function δ over input alphabet Σ on each state s.t. it should
accept the string which ends with ab. We need to verify whether transition for each input symbol on
each state is valid or invalid by testing the input string as shown below:
We have the transitions
δ(q0, a) = q1
 δ(q1, b) = q2
And We need to identify the remaining transition Function as shown below
δ(q0, b) =?
δ(q1, a) =?
δ(q2, a) =?
δ(q2, b) =?
For The Transition δ(q0, b) =?
•​ If the transition function is δ(q0, b) = q1, then the input string W = bb will also be accepted even
though it is invalid string & not ending with ab. Hence this transition function δ(q0, b) = q1 is not
valid.
•​ If the transition function is δ(q0, b) = q2, then the input string W = b will also be accepted even
though it is invalid string. Hence this transition function δ(q0, b) = q2 is not valid.
•​ If the transition function is δ(q0, b) = q0, then the input string W = bbab and other valid input string
will be accepted. Hence the Transition Function is δ(q0, b) = q0 is valid.
For The Transition δ(q1, a) =?
If the transition function is δ(q1, a) = q0, then the input string W = aab will not be accepted even though it is valid
string. Hence this transition function δ(q1, a) = q0 is not valid.
•​ If the transition function is δ(q1, a) = q2, then the input string W = aa will also be accepted even
though it is invalid string. Hence this transition δ(q1, a) = q2 is not valid.
•​ If the transition function is δ(q1, a) = q1, then the input string W = aab and other valid string will
be accepted. Hence this Transition Function is δ(q1, a) = q1 is valid.
For The Transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W = abab will not be accepted even
though it is valid string. Hence this transition δ(q2, a) = q0 is not valid.
•​ If the transition function is δ(q2, a) = q2, then the input string W = aba will also be accepted even
though it is invalid string. Hence this transition δ(q2, a) = q2 is not valid.
•​ If the transition function is δ(q2, a) = q1, then the input string W = abab & other valid string will be
accepted. Hence this Transition Function is δ(q2, a) = q1 is valid.
For The Transition δ(q2, b) =?
•​ If the transition function is δ(q2, b) = q1, then the input string W = abb will also be accepted even
though it is invalid string. Hence this transition δ(q2, b) = q1 is not valid.
•​ If the transition function is δ(q2, b) = q2, then the input string W = abb will also be accepted even
though it is invalid string. Hence this transition δ(q2, b) = q2 is not valid.
•​ If the transition function is δ(q2, b) = q0, then the input string W = abbab & other valid strings will
be accepted. Hence the Transition Function is δ(q2, b) = q0 is valid
Step 3: Constructing the Final Transition Table and Transition Diagram
Transition Table:

δ a b
→ q0 q1 q0
 q1 q1 q2
q2
q1 q0
Transition Diagram:
b​ a

start

Substring problems
The same procedure has to be followed as we have seen in the previous sections example.
Example 17 Design a DFSN to accept the strings of a’s and b’s having substring ab.
Step 1: Input Alphabet Σ = {a, b}, MS = bb and three states are required to construct minimum state transition
diagram and accept ab. The state transition Diagram for Minimum String is as shown below:

start
Step 2: Constructing the remaining transition function δ over the input alphabet Σ on each state by
testing the input string as shown below:
 We have the transitions
δ(q0, a) = q1
δ(q1, b) = q2
And We need to identify the remaining transition Function as shown below
δ(q0, b) =?
δ(q1, a) =?
δ(q2, a) =?
δ(q2, b) =?
For The Transition δ(q0, b) =?
•​ If the transition function is δ(q0, b) = q1, then the input string W = ba will also be accepted even
though it is invalid string. Hence this transition δ(q0, b) = q1 is not valid.
•​ If the transition function is δ(q0, b) = q2, then the input string W = b will also be accepted even
though it is invalid string. Hence this transition δ(q0, b) = q2 is not valid.
•​ If the transition function is δ(q0, b) = q0, then the input string W = ab and other valid string will
also be accepted. Hence the Transition Function δ(q0, b) = q0 is valid.
For The Transition δ(q1, a) =?
•​ If the transition function is δ(q1, a) = q0, then the input string W = aab will not be accepted even
though it is valid string. Hence this transition function δ(q1, a) = q0 is not valid.
•​ If the transition function is δ(q1, a) = q2, then the input string W = aa will also be accepted even
though it is invalid string. Hence this transition function δ(q1, a) = q2 is not valid.
•​ If the transition function is δ(q1, a) = q1, then the input string W = aab & other valid string will be
accepted. Hence this Transition Function is δ(q1, a) = q1 is valid.
For The Transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W = aba will not be accepted even
though it is valid string. Hence this transition function δ(q2, a) = q0 is not valid.
•​ If the transition function is δ(q2, a) = q1, then the input string W = aba will not be accepted even
though it is valid string. Hence this transition function δ(q2, a) = q1 is not valid.
•​ If the transition function is δ(q2, a) = q2, then the input string W = aba & other valid string will
also be accepted. Hence this Transition Function is δ(q2, a) = q2 is valid.
For The Transition δ(q2, b) =?
•​ If the transition function is δ(q2, b) = q0, then the input string W = abb will not be accepted even
though it is valid string. Hence this transition function δ(q2, b) = q1 is not valid.
•​ If the transition function is δ(q2, b) = q1, then the input string W = abb will not be accepted even
though it is valid string. Hence this transition function δ(q2, b) = q1 is not valid.
•​ If the transition function is δ(q2, b) = q2, then the input string W = abb & other valid strings will
also be accepted. Hence the Transition Function δ(q2, b) = q2 is valid.
Step 3: Constructing the Final Transition Table and Transition Diagram
Transition Table:

δ a b
→ q0 q1 q0
q1 q1 q2
q2
q2 q2

Transition Diagram:
Even and Odd Problems
Example 18 Design a DFSA to accept the even number of a’s or Design a DFSA for the language
L = {a2n | n ⩾0}
Step 1: In this example, the even numbers are 0, 2, 4, 6, 8.....etc.
The input alphabet Σ = {a}, Minimum String is NULL or aa.
Hence the DFSA should accept the string {ϵ, aa, aaaa, aaaaaa.....} and so on.
The Transition diagram for the minimum string is as shown below:

Both the diagram combined together

start

Step 2: Constructing the Remaining transition function which are not present in the above transition
diagram. We have only the transition
δ(q0, a) = q1
δ(q1, a) = q2
And We need to identify the transition for the
δ(q2, a) =?
For the transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W = aaa will also be accepted even
though it is invalid string which is odd number of a’s. Hence this transition function δ(q2, a) = q0 is
not valid.
•​ If the transition function is δ(q2, a) = q2, then the input string W = aaaaa will also be accepted
even though it is invalid string. Hence this transition function δ(q2, a) = q2 is not valid.
•​ If the transition function is δ(q2, a) = q1, then W = aa & other valid string will also be accepted.
Hence this transition function δ(q2, a) = q1 is valid.
Step 3: The final Transition Diagram and Transition Table
Transition Table:
δ a
q0
→ q1
q1 q2
q2
q1
Transition Diagram:

Or

Example
Design a DFSA to accept the odd number of a’s or Design a DFSA for the language L = {a2n+1 | n ⩾0}
Step 1: In this example odd numbers are 1, 3, 5, 7, 9.....etc. The input alphabet Σ = {a}, Minimum String is MS=a.
Hence the DFSA should accept the strings of a, aaa, aaaaa and so on. The Transition diagram for the minimum
string is as shown below:

Step 2: Constructing the Remaining transition function which are not present in the above transition
diagram. So we have only the transition

δ(q0, a) = q1
We need to identify the transition for the
δ(q1, a) =?
For the transition δ(q1, a) =?
•​ If the transition function is δ(q1, a) = q1, then the input string W = aa or aaaa and so on will also
be accepted even though it is invalid string. Hence this transition function δ(q1, a) = q1 is not valid.
•​ If the transition function is δ(q1, a) = q0, then W = aaa, aaaaa & other valid string will also be
accepted. Hence this transition δ(q1, a) = q0 is valid.
Step 3: The final Transition Diagram and Transition Table
Transition Table:

δ a
→ q0 q1
q1
q0

Transition Diagram:
Example
Design a DFSA for the language L = {W | |W | modulo 2 = 0 where W ∈ (a + b)∗}
Step 1: In this example, the length of the string must be even, then remainder will be always 0. Hence
we require two states to accept even length. The input alphabet = {a, b}, Minimum String MS=ab or
ba or bb or aa. The Transition diagram for the minimum string is as shown below:

start
a,b

Step 2: Constructing the Remaining transition function which are not present in the above transition diagram.
So we have only the transition

δ(q0, a) =
q1 δ(q0, b)
= q1 δ(q1,
a) = q0
δ(q1, b) =
q0
We have all the transitions and need not identify the any other transition
Step 3: Hence the final Transition Diagram and Transition Table
Transition Table:
δ a b
q0
→ q1 q1
q1 q0 q0

Transition Diagram:

Consecutive problems
The same procedure need to be followed as we have seen in the previous sections example.
Example 21 Design a DFSN to accept the strings of 0’s and 1’s having two consecutive 1’s.
Step 1: Input Alphabet Σ = {0, 1}, MS = 11 and three states are required to construct state transition
diagram for minimum string and accept 11. The state transition Diagram for Minimum String is as
shown below:
 start
Step 2: Constructing the remaining transition function δ over the input alphabet Σ on each state. So we
need to verify whether transition on each state is valid or invalid by testing the input string as shown
below:
We have the transitions
δ(q0, 1) = q1
δ(q1, 1) = q2
And We need to identify the remaining transition Function as shown below
δ(q0, 0) =?
δ(q1, 0) =?
δ(q2, 0) =?
δ(q2, 1) =?
For The Transition δ(q0, 0) =?
•​ If the transition function is δ(q0, 0) = q1, then the input string W = 01 will also be accepted even
though it is invalid string. Hence this transition δ(q0, 0) = q1 is not valid.
•​ If the transition function is δ(q0, 0) = q2, then the input string W = 0 will also be accepted even
though it is invalid string. Hence this transition δ(q0, 0) = q2 is not valid.
•​ If the transition function is δ(q0, 0) = q0, then string W = 0011 and other valid string will also be
accepted. Hence the Transition Function δ(q0, b) = q0 is valid.
For The Transition δ(q1, 0) =?
•​ If the transition function is δ(q1, 0) = q1, then the input string W = 101 will be accepted even
though it is invalid string. Hence this transition function δ(q1, 0) = q1 is not a valid.
•​ If the transition function is δ(q1, 0) = q2, then the input string W = 10 will also be accepted even
though it is invalid string. Hence this transition function δ(q1, 0) = q2 is not a valid.
•​ If the transition function is δ(q1, 0) = q1, then the input string W = 001011 and other valid strings
will be accepted. Hence this Transition Function δ(q1, 0) = q1 is valid.
For The Transition δ(q2, 0) =?
•​ If the transition function is δ(q2, 0) = q0, then the input string W = 110 will not be accepted even
though it is valid string. Hence this transition function δ(q2, 0) = q0 is not a valid.
•​ If the transition function is δ(q2, 0) = q1, then the input string W = 110 will not be accepted even
though it is valid string. Hence this transition function δ(q2, 0) = q1 is not a valid.
•​ If the transition function is δ(q2, 0) = q2, then the input string W = 110 & other Valid string will be
accepted. Hence this Transition Function δ(q2, 0) = q2 is valid.
For The Transition δ(q2, 1) =?
•​ If the transition function is δ(q2, 1) = q0, then the input string W = 111 will not be accepted even
though it is valid string. Hence this transition function δ(q2, 1) = q0 is not valid.
•​ If the transition function is δ(q2, 1) = q1, then the input string W = 111 will not be accepted even
though it is valid string. Hence this transition δ(q2, 1) = q1 is not valid.
 •​ If the transition function is δ(q2, 1) = q2, then the input string W = 111 & other valid strings will be
accepted. Hence the remaining Transition Function δ(q2, 1) = q2 is valid.
Step 3: Constructing the Final Transition Table and Transition Diagram
Transition Table:

δ 0 1
→ q0 q0 q1
q1 q0 q2
q2
q2 q2

Transition Diagram:

Followed-by problems
For this also the same procedure has to be followed as we have seen in the previous example.
Example 22 Design a DFSA to accept the strings of a’s and b’s where a is followed by b.
Step 1: Input Alphabet Σ = {a, b}, MS = (ϵ, ab) and three states are required to construct minimum state
transition diagram and accept ab. So each a will be followed by b. The state transition Diagram for
Minimum String is as shown below:

start
Step 2: Constructing the remaining transition function δ over input alphabet Σ on each state. We need to
verify whether transition for each input symbol on each state is valid or not by testing the input string
as shown below:
Here we have the transitions
δ(q0, a) = q1
δ(q1, b) = q2
And We need to identify the remaining transition Function as shown below
δ(q0, b) =?
δ(q1, a) =?
δ(q2, a) =?
δ(q2, b) =?
For The Transition δ(q0, b) =?
 •​ If the transition function is δ(q0, b) = q1, then the input string W=bb will also be accepted even
though it is invalid string. Hence this transition function δ(q0, b) = q1 is not valid.
•​ If the transition function is δ(q0, b) = q2, then the input string W=b will also be accepted even
though it is invalid string. Hence this transition function δ(q0, b) = q2 is not valid.
•​ If the transition function is δ(q0, b) = q0, then the input string W=bab and other valid string will
also be accepted. Hence the Transition Function δ(q0, b) = q0 is valid.
For The Transition δ(q1, a) =?
•​ If the transition function is δ(q1, a) = q0, then the input string W=aaab will also be accepted even
though it is invalid string, because a is not followed by b. Hence this transition function δ(q1, a) =
q0 is not a valid.
•​ If the transition function is δ(q1, a) = q2, then the input string W=aa will also be accepted even
though it is invalid string. Hence this transition function δ(q1, a) = q2 is not a valid.
•​ If the transition function is δ(q1, a) = q1, then the input string W=aaab will also be accepted. Hence
this Transition Function is δ(q1, a) = q1 is invalid.
•​ So left out transition is that it has to move to trap state i.e. Transition Function is δ(q1, a) = trap
is valid. For The Transition δ(q2, a) =?
•​ If the transition function is δ(q2, a) = q0, then the input string W=abab will not be accepted even
though it is valid string. Hence this transition function δ(q2, a) = q0 is not a valid.
•​ If the transition function is δ(q2, a) = q2, then the input string W=aba will also be accepted even
though it is invalid string. Hence this transition function δ(q2, a) = q2 is not a valid.
•​ If the transition function is δ(q2, a) = q1, then the input string W=abab & other valid string will
also be accepted. Hence this Transition Function δ(q2, a) = q1 is valid.
For The Transition δ(q2, b) =?
•​ If the transition function is δ(q2, b) = q0, then the input string W=abb will not be accepted even
though it is valid string. Hence this transition function δ(q2, b) = q1 is not valid.
•​ If the transition function is δ(q2, b) = q1, then the input string W=abb will not be accepted even
though it is valid string. Hence this transition function δ(q2, b) = q1 is not valid.
•​ If the transition function is δ(q2, b) = q2, then the input string W=abb & other valid strings will
also be accepted. Hence the Transition Function δ(q2, b) = q2 is valid.
Step 3: Constructing the Final Transition Table and Transition Diagram
Transition Table:

δ a b
→ q0 q1 q0
q1 trap q2
q2
q1 q2
trap trap trap
Transition Diagram:
 b​ b

start

a,b

Combination Problems
Example 23 Design a DFSA to accept the strings of 0’s and 1’s starting with 01 and ending with 10 or
for the language L = {01W 10|W ∈ (0 + 1)∗}
Step 1: Input Alphabet Σ = {0, 1}, MS = 0110 and five states are required to accept MS. The state
transition Diagram for Minimum String is as shown below:

start

Step 2: Constructing the remaining transition function δ over the input alphabet Σ on each state. So we
need to verify whether transition on each state for each input symbol is valid or not by testing the input
string as shown below:
We have the transitions
δ(q0, 0) =
q1 δ(q1, 1)
= q2 δ(q2,
1) = q3
δ(q3, 0) =
q4
And We need to identify the remaining transition Function as shown below
δ(q0, 1) =?
δ(q1, 0) =?
δ(q2, 0) =?
δ(q3, 1) =?
δ(q4, 0) =?
δ(q4, 1) =?
For The Transition δ(q0, 1) =?
•​ If the transition function is δ(q0, 1) = q1, then the input string W=1110 will also be accepted even
though it is invalid string. Hence this transition function δ(q0, 1) = q1 is not valid.
•​ If the transition function is δ(q0, 1) = q2, then the input string W=110 will also be accepted even
though it is invalid string. Hence this transition function δ(q0, 1) = q2 is not valid.
 •​ If the transition function is δ(q0, 1) = q3, then the input string W=10 will also be accepted even
though it is invalid string. Hence this transition function δ(q0, 1) = q3 is not valid.
•​ If the transition function is δ(q0, 1) = q4, then the input string W=0 will also be accepted even
though it is invalid string. Hence this transition function δ(q0, 1) = q4 is not valid.
•​ If the transition function is δ(q0, 1) = q0, then the input string W=110110 will also be accepted
even though it is invalid string. Hence this transition function δ(q0, 1) = q0 is not valid.
•​ Hence the for this transition it will move to trap state. δ(q0, 1) = trap
For The Transition δ(q1, 0) =?
•​ If the transition function is δ(q1, 0) = q0, then the input string W=000110 will also be accepted
even though it is invalid string. Hence this transition function δ(q1, 0) = q0 is not a valid.
•​ If the transition function is δ(q1, 0) = q2, then the input string W=0010 will also be accepted even
though it is invalid string. Hence this transition function δ(q1, 0) = q2 is not a valid.
•​ If the transition function is δ(q1, 0) = q3, then the input string W=000 will also be accepted even
though it is invalid string. Hence this Transition Function δ(q1, 0) = q3 is invalid.
•​ If the transition function is δ(q1, 0) = q4, then the input string W=00 will also be accepted even
though it is invalid string. Hence this Transition Function δ(q1, 0) = q4 is invalid.
•​ If the transition function is δ(q1, 0) = q1, then the input string W=000110 will also be accepted
even though it is invalid string. Hence this Transition Function δ(q1, 0) = q1 is invalid.
•​ So left out transition is that it has to move to trap state i.e. Transition Function δ(q1, 1) = trap
is valid. For The Transition δ(q2, 0) =?
•​ If the transition function is δ(q2, 0) = q0, then the input string W=01001 will not be accepted even
though it is valid string. Hence this transition function δ(q2, 0) = q0 is not a valid.
•​ If the transition function is δ(q2, 0) = q1, then the input string W=01001 will not be accepted even
though it is valid string. Hence this transition function δ(q2, 0) = q1 is not a valid.
•​ If the transition function is δ(q2, 0) = q3, then the input string W=0100 will also be accepted even
though it is invalid string. Hence this Transition Function δ(q1, 0) = q3 is invalid.
•​ If the transition function is δ(q2, 0) = q4, then the input string W=010 will also be accepted even
though it is invalid string. Hence this Transition Function δ(q2, 0) = q4 is invalid.
•​ If the transition function is δ(q2, 0) = q2, then the input string W=0100010 and all other valid
strings will also be accepted. Hence this Transition Function δ(q2, 0) = q2 is valid.
For The Transition δ(q3, 1) =?
•​ If the transition function is δ(q3, 1) = q0, then the input string W=01110 will not be accepted even
though it is valid string. Hence this transition function δ(q3, 1) = q0 is not valid.
•​ If the transition function is δ(q3, 1) = q1, then the input string W=01110 will not be accepted even
though it is valid string. Hence this transition function δ(q3, 1) = q1 is not valid.
•​ If the transition function is δ(q3, 1) = q2, then the input string W=01110 will not be accepted even
though it is valid string. Hence this transition function δ(q3, 1) = q2 is not valid.
•​ If the transition function is δ(q3, 1) = q4, then the input string W=0111 will also be accepted even
though it is invalid string. Hence this transition function δ(q3, 1) = q4 is not valid.
 •​ If the transition function is δ(q3, 1) = q3, then the input string W=01110 and all other valid strings
will also be accepted. Hence this transition function δ(q3, 1) = q3 is a valid.
For The Transition δ(q4, 0) =?
•​ If the transition function is δ(q4, 0) = q0, then the input string W=0110010 will not be accepted
even though it is valid string. Hence this transition function δ(q4, 0) = q0 is not valid.
•​ If the transition function is δ(q4, 0) = q1, then the input string W=0110010 will not be accepted
even though it is valid string. Hence this transition function δ(q4, 0) = q1 is not valid.
•​ If the transition function is δ(q4, 0) = q3, then the input string W=011000 will also be accepted
even though it is invalid string. Hence this transition function δ(q4, 0) = q3 is not valid.
•​ If the transition function is δ(q4, 0) = q4, then the input string W=01100000 will also be accepted
even though it is invalid string. Hence this transition function δ(q4, 0) = q4 is not valid.
•​ If the transition function is δ(q4, 0) = q2, then the input string W=0110010 and all other valid
strings will also be accepted. Hence this transition function δ(q4, 0) = q2 is a valid.
For The Transition δ(q4, 1) =?
•​ If the transition function is δ(q4, 1) = q0, then the input string W=011010 will not be accepted even
though it is valid string. Hence this transition function δ(q4, 1) = q0 is not valid.
•​ If the transition function is δ(q4, 1) = q1, then the input string W=011010 will not be accepted even
though it is valid string. Hence this transition function δ(q4, 1) = q1 is not valid.
•​ If the transition function is δ(q4, 1) = q2, then the input string W=011010 will not be accepted even
though it is valid string. Hence this transition function δ(q4, 1) = q2 is not valid.
•​ If the transition function is δ(q4, 1) = q4, then the input string W=01101111 will also be accepted
even though it is invalid string. Hence this transition function δ(q4, 1) = q4 is not valid.
•​ If the transition function is δ(q4, 1) = q3, then the input string W=011010 and all other valid strings
will also be accepted. Hence this transition function δ(q4, 1) = q3 is a valid.
Step 3: Constructing the Final Transition Table and Transition Diagram

δ 0 1
→ q0 q1 trap
q1 trap q2
q2 q2 q3
q3 q4 q3
q4
q2 q3
trap trap trap
Transition Diagram:0​ 1

start
 0,1

Now here on-words only exact solution will be given based on the method which we followed in previous sections.
Example 24 Design the DFA to accept the strings of a’s and b’s starting with aa and ending with bb or
for the language L = {aaWbb | W ∈ (a + b)∗}
Final Transition Table:
δ a b
→ q0 q1
q1 q2
q2 q2 q3
q3 q2 q4
q4
q2 q4

Example Design the DFSA to accept the strings of a’s and b’s starting with a followed by ba and
ending with ab or for the language L = {abaWab | W ∈ (a + b)∗}
Final Transition Table:

δ a b
→ q0 q1 trap
q1 trap q2
q2 q3 trap
q3 q4 q3
q4 q4 q5
q5
q4 q3
trap trap trap

Transition Diagram:
b

start

a,b

Example 26 Design the DFSA to accept the strings of a’s and b’s starting with even number of a’s
followed by odd number of b’s or for the language L = {(aa)nb(bb)m | n, m ⩾ 0} or L = {a2nb2m+1 | n, m ⩾
0}Final Transition Table:

δ a b
→ q0 q1 q3
q1 q2 trap
q2 q1 q3
q3
trap q2
trap trap trap
Transition Diagram:

start

a,b

Divisible by K-Problems
In this method, designing of DFSA for the binary and decimal numbers whose value can be divisible by
k is discussed and shown bellow
j=(r ∗ i+d) modulo k
where r is the radix (Length of input alphabet), i is the remainder which represents states of DFSA, d is
the input alphabet, k is the divisor and j is the value which represents the next state.
Radix for Binary and decimal numbers as shown bellow
r = {0, 1} = 2
r = {0, 1, 2, 3,​ 9} = 10
1.​Identify the Input alphabet d, radix r (Length of input alphabet) and divisor k.
2.​Compute the remainder i by using the divisor k will be represented the states of DFSA.
3.​Construct the transition function by using δ(qi, a) = qj where j=(r ∗ i+d) modulo k
4.​Identify the start state and set of final states by testing and processing the valid input strings.
5.​Draw the transition table and transition diagram for the constructed transition function.
Example 27 Design the DFSA to accept the strings of 0’s and 1’s, the value of each string will be
represented as a binary. The language should accept the string only zero modulo 3 (0mod3).
Step 1: Input alphabet d = {0, 1}, radix r =2 and divisor k =3.
Step 2: Computing the remainders i by using k. the remainders will be {0, 1, 2}.
Step 3: Transition Functions by using the δ(qi, a) = qj where j=(r ∗ i+d) mod k as shown below.

Remainder i d 2 ∗ i+d mod 3=j δ(qi, d) = qj

0 0 2 ∗ 0+0 mod 3=0 δ(q0, 0) = q0
1 2 ∗ 0+1 mod 3=1 δ(q0, 1) = q1
1 0 2 ∗ 1+0 mod 3=2 δ(q1, 0) = q2
1 2 ∗ 1+1 mod 3=0 δ(q1, 1) = q0
2 0 2 ∗ 2+0 mod 3=1 δ(q2, 0) = q1
1 2 ∗ 2+1 mod 3=2 δ(q2, 1) = q2
the transition Table is

δ 0 1
→ q0 q0 q1
q1 q2 q0
q2
q1 q2
Transition Diagram is
0​ 1

start
1​ 0

Example 28 Design the DFSA to accept the strings of 0’s and 1’s, the value of each string will be
represented as a binary. The language should accept the string only zero modulo 5 (0mod5).
Step 1: Input alphabet d = {0, 1}, radix r =2 and divisor k =5.
Step 2: Computing the remainders i by using k. The remainders {0, 1, 2, 3, 4} will be the states of
DFSA. Step 3: Transition Functions by using the δ(qi, a) = qj where j=(r ∗ i+d) modulo k as shown
below.

Remainder i d 2 ∗ i+d mod 3=j δ(qi, d) = qj

0 0 2 ∗ 0+0 mod 5=0 δ(q0, 0) = q0
1 2 ∗ 0+1 mod 5=1 δ(q0, 1) = q1
1 0 2 ∗ 1+0 mod 5=2 δ(q1, 0) = q2
1 2 ∗ 1+1 mod 5=3 δ(q1, 1) = q3
2 0 2 ∗ 2+0 mod 5=4 δ(q2, 0) = q4
1 2 ∗ 2+1 mod 5=0 δ(q2, 1) = q0
3 0 2 ∗ 3+0 mod 5=1 δ(q3, 0) = q1
1 2 ∗ 3+1 mod 5=2 δ(q3, 1) = q2
4 0 2 ∗ 4+0 mod 5=3 δ(q4, 0) = q3
1 2 ∗ 4+1 mod 5=4 δ(q4, 1) = q4
The transition Table is

δ 0 1
q0
→ q0 q1
q1 q2 q3
q2 q4 q0
q3 q1 q2
q4 q3 q4
Transition Diagram is
Example 29 Design the DFSA to accept the decimal numbers zero modulo 2 (0mod2).
Step 1: Input alphabet d = {0, 1, 2, 3​9}, radix r =10 and divisor k =2.
Step 2: Computing the remainders i by using k. the remainders {0, 1} will be states of DFSA. Here the
remainder 0 will be from the input alphabet {0, 2, 4, 6, 8} and the remainder 1 from {1, 3, 5, 7, 9}.
Step 3: Transition Function can be obtain by using the δ(qi, a) = qj where j=(r ∗ i+d) modulo k as shown below.

Remainder i d 2 ∗ i+d mod 3=j δ(qi, d) = qj

0 0 10 ∗ 0+0 mod δ(q0, 0) = q0
1 2=0 δ(q0, 1) = q1
10 ∗ 0+1 mod
2=1
1 0 10 ∗ 1+0 mod δ(q1, 0) = q0
1 2=0 δ(q1, 1) = q1
10 ∗ 1+1 mod
2=1
The transition Table is

δ 0,2,4,6,8 1,3,5,7,9
q0
→ q0 q1
q1 q0 q1

Transition Diagram is

Modulo K-Counter problem

Designing of DFSA for the language over length of input alphabet modulo k is discussed in this
section. For example string with even length, odd length, even & odd length and vise-varsa. The
general transition diagram for string of even and odd length of input alphabet a,b is shown below
where q0 represents accepting state for Even number of a’s & even number of b’s, q1 represents
accepting state for Even number of a’s & odd number of b’s, q2 represents the accepting state for odd
number of a’s & even number of b’s and q3 represents accepting state for odd number of a’s & odd
number of b’s.

If the DFSA accepts the even number of a’s and Even number of b’s, then q0 will be the final state. If
the DFSA accepts Even number of a’s & odd number of b’s, then q1 will be the final state. If the DFSA
accepts odd number of a’s & even number of b’s, then q2 will be the final state. If the DFSA accepts
odd number of a’s & odd number of b’s, then q3 will be the final state.
Example 30 Design the DFSA for the language L = {w | na(w) mod 3 = 0&nb(w) mod 2 = 0}
The number of a’s will be multiple of three, will get the remainders 0,1,2, that means DFSA should
include three states to accept the na(w)mod3 = 0 and number of b′s will be multiple of two, will get the
remainders 0,1, that means DFSA should include two states to accept the nb(w)mode2 = 0. So total six
states are required to construct the complete DFSA for the given example.

Example 31 Design the DFSA for the language L = {w | na(w) mod 3 = 0&nb(w) mod 3 = 0}.
The number of a’s will be multiple of three, will get the remainders 0,1,2, that means DFSA should
include three states to accept the na(w)mod3 = 0 and the number of b’s will also be multiple of three,
will get the remainders 0,1,2, that means DFSA should include three states to accept the nb(w)mode3 =
0. So total nine states are required to construct the complete DFSA for the given problem.

b
Example 32 Design a DFSA to accept the strings over the input alphabet {0, 1}. The set of all strings
beginning with 101.
Σ
= {0, 1}, Q = {q0, q1, q2, q3, trap, }
Transition Table:

δ 0 1
→ q0 trap q1
q1 q2 trap
q2 trap q3
q3
q3 q3
trap trap trap
Transition Diagram:
0,1

start

0,1

Example 33 Design a DFSA to accept the strings over the alphabet {0, 1}. The set of all strings
containing 1101 as a substring with 101.
Σ
= {0, 1}, Q = {q0, q1, q2, q3, q4}
Transition Table:

δ 0 1
→ q0 q0 q1
q1 q0 q2
q2 q3 q2
q3 q0 q4
q4
q4 q4
Transition Diagram:
0​ 1

start
 0

Example 34 Design a DFSA to accept the strings over the alphabet {0, 1}. The set of all strings with
exactly three consecutive 0’s.
 Σ
= {0, 1}, Q = {q0, q1, q2, q3, q4}
Transition Table:

δ 0 1
→ q0 q1 q0
q1 q2 q0
q2 q3 q0
q3
q4 q3
q4 q4 q4
Transition Diagram:
1​ 1

start

1​ 0,1

Example 35 Design a DFSA to accept the strings over the alphabet {0, 1} Such that, the set of all
strings s.t the number of 1’s is even and the number of 0’s is a multiple of 3.
Σ
= {0, 1}, Q = {q0, q1, q2, q3, q4, q5}
Transition Diagram:

Example 36 Design a DFSA to accept the strings over the alphabet {0, 1} Such that, the set of all
strings not containing 110.
Σ
= {0, 1}, Q = {q0, q1, q2, q3}
Transition Table:
 δ 0 1
q0
→ q0 q1
q1
q0 q2
q2
q3 q2
q3 q3 q3

Transition Diagram: 1​ 0,1

0

start
0

Example 37 Example: Design a DFSA to accept the strings over the alphabet {0, 1} Such that, the set
of all strings that begin with 01 and end with 11.
Σ
= {0, 1}, Q = {q0, q1, q2, q3, q4, q5}
Transition Table:

δ 0 1
→ q0 q1 q5
q1 q5 q2
q2 q2 q3
q3 q5 q4
q4
q2 q4
q5 q5 q5
Transition Diagram:
0,1

start
 1

Example 38 Design a DFSA to accept the strings over the alphabet {0, 1} Such that, the set of all
strings which when interpreted as a binary integer is a multiple of 3.
d = {0, 1}, k=3, i = {0, 1, 2},Q = {q0, q1, q2} r=2.

Remainder i d 2 ∗ i+d mod 3=j δ(qi, d) = qj

0 0 2 ∗ 0+0 mod 3=0 δ(q0, 0) = q0
1 2 ∗ 0+1 mod 3=1 δ(q0, 1) = q1
1 0 2 ∗ 1+0 mod 3=2 δ(q1, 0) = q2
1 2 ∗ 1+1 mod 3=0 δ(q1, 1) = q0
2 0 2 ∗ 2+0 mod 3=1 δ(q2, 0) = q1
1 2 ∗ 2+1 mod 3=2 δ(q2, 1) = q2
Transition Table:

δ 0 1
→ q0 q0 q1
q1 q2 q0
q2
q1 q2
Transition Diagram:
0​ 1

start
1​ 0

Example 39 Design a DFSA to accept the language over the input alphabet {0, 1} s.t. the set of all
strings beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5. For example,
strings 101, 1010, and 1111 are in the language; 0, 100, and 111 are not.
d = {0, 1}, k=5, i = {0, 1, 2, 3, 4},Q = {q0, q1, q2, q3, q4} r=2

Remainder i d 2 ∗ i+d mod 3=j δ(qi, d) = qj

0 0 2 ∗ 0+0 mod 5=0 δ(q0, 0) = q0
1 2 ∗ 0+1 mod 5=1 δ(q0, 1) = q1
1 0 2 ∗ 1+0 mod 5=2 δ(q1, 0) = q2
1 2 ∗ 1+1 mod 5=3 δ(q1, 1) = q3
2 0 2 ∗ 2+0 mod 5=4 δ(q2, 0) = q4
1 2 ∗ 2+1 mod 5=0 δ(q2, 1) = q0
3 0 2 ∗ 3+0 mod 5=1 δ(q3, 0) = q1
1 2 ∗ 3+1 mod 5=2 δ(q3, 1) = q2
4 0 2 ∗ 4+0 mod 5=3 δ(q4, 0) = q3
1 2 ∗ 4+1 mod 5=4 δ(q4, 1) = q4
transition Table:

δ 0 1
→ q5 ϕ q1
q0
q0 q1
q1 q2 q3
q2 q4 q0
q3 q1 q2
q4 q3 q4
Transition Diagram:
 start

Example 40 Design a DFSA to accept the language over the input alphabet {0, 1} s.t. the set of all
strings when interpreted in reverse as a binary integer, is a multiple of 5. For example, strings 0 10011,
1001100, and 0101 are in the language.
d = {0, 1}, k=5, i = {0, 1, 2, 3, 4},Q = {q0, q1, q2, q3, q4} r=2
It is same as previous problem except the transition from q5 to q1, but all the transitions will be in
reverse direction as shown below
Transition Diagram:
0

start

Example 41 Design a DFSA to accept the set of all strings beginning with 101.
Transition Diagram:
0,1

start

0,1
Example 42 Design a DFSA to accept the set of all strings containing 1101 as a substring.
Transition Diagram:
 0 1​ 0,1

start

Example 43 Design a DFSA to accept the set of all strings with exactly three consecutive 0’s.

Transition Diagram: 1​ 0,1

1

start

Example 44 Design a DFSA to accept the set of all strings not containing 110.

Transition Diagram: 1​ 0,1

0

start
0

Example 45 Design a DFSA to accept the set of all strings that begin with 01 and end with 11.
Transition Diagram:
0​ 0​ 1

start

Example 46 Design a DFSA toa accept the set of all string such that the number of 1’s is even and the
number of 0’s is a multiple of 3.
Transition Diagram:
 0

Example 47 2014 dec, 06cs56 1b i

Transition Diagram: a,b

b​ a

start
a

Example 48 2014 dec, 06cs56 1b ii

Transition Diagram:
b​ b​ b​ b

start

Example 49 2014 dec, 06cs56 1b iii

Transition Diagram: b​ a

start
Example 50 2012 dec, 10cs56 1b
Transition Diagram:
 start

Example 51 2011 june, cs44 1b

Transition Diagram:
b​ a

start

Example 52 Dec 2008 06cs56 1b

Transition Diagram:
a,b

start

b​ b

Theorem 2 Prove that for any state q, string x & input symbol a,
δˆ(q, ax) = δˆ(δ(q, a), X)
Proof.
Basis: Let assume that, by the definition of extended transition function
δˆ(q, a) = p
δˆ(q, ϵ) = q
δ(q, a) = p
Review Questions
 1.​Define DFA?
2.​What are the components of finite Automata?
3.​Define language of DFA

1.3.7​ Exercises
1.​Design a DFSA that recognize the language L = {W | Wstartswith0andhasoddlength,
orstartswith1andhasevenlength}
2.​Design a DFSA that recognize the language L = {W | Wisnon − emptyandhas1oneveryoddposition}
3.​Design a DFSA that recognize the following languages over the input alphabet Σ = {0, 1}

(a)​L = {W | W is string having no two consecutive 0’s}

(b)​L = {W | W is string having substring 00, ends and begins with same symbol}
(c)​L = {W | W is multiple of 8 when interpreted as a binary integer}
(d)​L = {W | W strings that begin or end with 00 or 11}
(e)​L = {W | W strings containing no more than one occurrence of the string 00. (The string 000
should be viewed as containing two occurrence of 00.)}
(f)​L = {W | W strings containing both 00 and 010 as sub strings}
(g)​L = {W | W strings that begin 0 and every 0 is followed by 1}
(h)​L = {W | W strings containing two consecutive zeros followed by two consecutive one}
(i)​L = {W | W strings that begin 0 and every 0 is followed by 1}
1.4​ Non-Deterministic Finite Automata (NFA)
All computers are deterministic and we can not find the non-deterministic computers. Now the question
is why do we need NDFSA?. As we already discussed that, DFSA is very difficult to construct and not
a powerful tool when the number of states increases. Hence to overcome this issue, the
Non-Deterministic Finite State Automata will be discussed which is very easy to construct and more
powerful than DFSA. The Non-Deterministic Finite State Automata has the more than one transition on
the same input symbol ∈ . So NDFSA will be in ambiguity to process the input string, because there
will be more than one transition on the same input alphabet.

For Example, the consider the transition diagram shown below is have more than one transition on
the input alphabet a. We have the transition function δ(q0, a) = q0, δ(q0, a) = q1 and δ(q0, a) = q2. Here it
indicates that there are three transitions on the same input symbol from the same state. Hence this kind
of automata is called as Non-deterministic Finite state automata.
a

start

1.4.1​ Formal view and Definition of NFA

The Definition of Non-deterministic finite state automata is same as Deterministic finite state automata,
but only difference in the transitions or transition function in which the NDFSA has more than one
transition on the same input symbol ∈ wherein only one transition on same input symbol ∈ in
DFSA. The definition of NDFSA as shown below.

NDFSA consist of 5-tuples (set of states, Input Alphabets, Transition function, Initial State, Set of
Accept- ing/final states).
N = (Q, Σ, δ, q0, F )

•​ Q is the set of states. In the above example Q = {q0, q1, q2}

•​ Σ is the set of input alphabet. In the above example Σ = {a, b}
•​δ is the set of transition functions. Mapping δ : QX Σ to Q. In the above example it has four
transitions in which three transition will move to next state on the same input symbol as shown
below.

δ(q0, a) =
q0 δ(q0, a)
= q1 δ(q0,
a) = q2
δ(q1, b) =
q2
The multiple transition on the same input symbol ∈ Σ from the same state will be represented as δ(q0, a) =

{q0, q1, q2} (For above example). Hence on each state for each input symbol may have the set of
transitions and represented as shown below.
 δ(q0, a) = {q0, q1, q2}, δ(q0, b) = ϕ
δ(q1, a) = ϕ, δ(q1, b) = {q2}

•​{q0} ∈ Q is the initial state of NDFSA.

•​F ∈ Q is the set of final states of NDFSA.
1.4.2​ Extended Transition Function δˆ to NDFSA
The extended transition function for NDFSA decides whether the input string will be accepted or
rejected by scan- ning the input string from Left to Right. It takes two arguments i.e current state q0 &
input string W and produces the output as set of state like {p1, p2, p3....pk} recursively. If the state {p1,
p2, p3 pk} in which any one of the state
∈ F then input string will be accepted, otherwise string will be rejected. This will be proved by
mathematical induction method. The input string will be divided into two part, i.e W = xα where x is the
remaining input string and α represents the last input symbol of the string. The remaining input string x
will keep on dividing into two part i.e x = xα recursively until it reaches to ϵ (x = ϵ), which basically
reach to the base condition.
Basis: δˆ(q0, ϵ) = {q0}. The transition from state q0 with out any input symbol or NULL symbol i.e ϵ
will be in the same state {q0}.
Induction: The input string will be divided into two part W = xα where x is the remaining input string and α
represents the last input symbol of the string. And the remaining input string x will keep on divided into two part
i.e x = xα recursively until it equals to ϵ (x = ϵ), it basically reach to the base condition as shown below.

δˆ(q0, W ) = δˆ(q0, xα)

δˆ(q0, xα) = δ(δˆ(q0, x),
α)
Let δˆ(q0, x) = {p1, p2, p3,​pi} then
δ({p1, p2, p3, ....pi}, α) = δ(p1, α) ∪ δ(p2, α) ∪ δ(p3, α)​ ∪ δ(pi, α)
Let δ(p1, α) ∪ δ(p2, α) ∪ δ(p3, α)...S...δ(pi, α) = {r1, r2, r3​ ri}
Hence this can be represented as m δ(pi, α) = {r1, r2, r3​ ri}
i=1

δˆ(q0, W ) = δˆ(q0, xα) = {r1, r2, r3​ri}

1.4.3​ Language of an NDFSA

The Language of Non-Deterministic Finite State automata N = (Q, Σ, δ, q0, F ) is denoted as L(N ) and can be
defined as
L = {W | W ∈ Σ∗ s.t δˆ(q0, W ) ∈ F }
The language of NDFSA N , is the set of string over Σ which takes input string from the start state & process it
and produces the output as next state which belongs to accepting state.

1.4.4​ Review Questions

1.​Define NFA?
2.​What are the components of finite Automata?
3.​Define language of NFA
4.​What are the deference between DFA and NFA?
1.4.5​ Examples of NDFSA
Example 53 Design the NDFSA to accept the language L={Wab|w ∈ (a + b)∗}
Transition Table:

δ a b
→ q0 {q0, q1} q0
q1 ϕ q2
q2
ϕ ϕ
Transition Diagram:
a,b

start

Example 54 Design the NDFSA to accept the language L={abWorWab|w ∈ (a + b)∗}

Transition Table:

δ a b
→ q0 {q0, q1, q3} q0
q1 ϕ q2
q2
q2 q2
q3 ϕ q4
q4
ϕ ϕ
Transition Diagram:
a,b

start
1.4.6​ Equivalence Deterministic and Non-Deterministic Finite State Automata (NFSA)
NFSA is easier to construct than DFSA, Since the all computers are the Deterministic, the NFSA has to be
converted
into DFSA. So the NFSA (N = (QN , Σ , δN , q0N , FN )) can be mapped to DFSA (D = (QD, Σ , δD, q0D, FD)).
There are two methods (Subset construction, Lazy evaluation) to convert from NFSA to DFSA as follows.
will be the input
Subset Construction Method
1. Σ​
​ Identify the Input Alphabet of DFSA. If is the

input alphabet of NFSA, then the Σ

alphabet of DFSA where Σ​ =​ .​ N​ D

D
2.​Identify the start state & final states of DFSA. If q0 is the start state of NDFSA, then {q0} will be
the start state of DFSA.
3.​Identify the states of DFSA: If the QN = {q0, q1, q2......qn} is the set of states of NDFSA, then the
states of DFSA will be all possible subset of states of NDFSA i.e QD = 2|QN |. If the set of states of
NDFSA Q
={q0, q1, q2}, then states of DFSA will be

QD = {ϕ, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}}
4.​Construct the transition function of DFSA over the input alphabet Σ​ on each state of DFSA.
5.​Construct the transition table over the transition function.
6.​Update the transition table by eliminating the unreachable states from the start state.
7.​Construct the final transition table and draw the state transition diagram.
Example 55 Obtain the equivalent DFSA from the following NFSA (ending with ab).
a,b

start
Step 1: Identify thΣe input alphabet of DFSA. The Input alphabet of DFSA Σ = {a, b} because the input alphabet
of the NDFSA is​ N = {a, b}
Step 2: Identifying the start state of DFSA. The start state of DFSA is {q0} because the start state of NDFSA is
{q0}.
Step 3: Identifying the set of states of DFSA. The states of NDFSA are QN = {q0, q1, q2}. So the states
of DFSA are QD = {ϕ, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}}.
Step 4: Constructing the transition functions for each input on each state of DFSA is given below.
δ(ϕ, a) = ϕ , δ(ϕ, b) = ϕ
δ(q0, a) = {q0, q1} , δ(q0, b) = {q0}
δ(q1, a) = {q0, q1} , δ(q1, b) = {q2}
δ(q2, a) = {ϕ} , δ(q2, b) = {ϕ}
δ({q0, q1}, a) = δ(q0, a) ∪ δ(q1, a) = {q0, q1} ∪ {ϕ} = {q0, q1}
δ({q0, q1}, b) = δ(q0, b) ∪ δ(q1, b) = {q0} ∪ {q2} = {q0, q2}
δ({q0, q2}, a) = δ(q0, a) ∪ δ(q2, a) = {q0, q1} ∪ {ϕ} = {q0, q1}
δ({q0, q2}, b) = δ(q0, b) ∪ δ(q2, b) = {q0} ∪ {ϕ} = {q0, q2}
δ({q1, q2}, a) = δ(q1, a) ∪ δ(q2, a) = {ϕ} ∪ {ϕ} = {ϕ}
δ({q1, q2}, b) = δ(q1, b) ∪ δ(q2, b) = {q2} ∪ {ϕ} = {q2}
δ({q0, q1, q2}, a) = δ(q0, a) ∪ δ(q1, a) ∪ δ(q2, a) = {q0, q1} ∪ {ϕ} ∪ {ϕ} = {q0, q1}
δ({q0, q1, q2}, b) = δ(q0, b) ∪ δ(q1, b) ∪ δ(q2, b) = {q0} ∪ {q2} ∪ {ϕ} = {q0, q2}
Step 5: Constructing the transition table for all transition function as shown below.
 δ a b
ϕ ϕ ϕ
→ {q0} {q0, q1} {q0}
{q1} ϕ {q2}
{q2}
ϕ ϕ
{q0, q1} {q0, q1} {q0, q2}

{q0, q2}
{q0, q1} {q0}

{q1, q2}
ϕ {q2}

{q0, q1, q2}

{q0, q1} {q1, q2}

Step 6: Updating the transition table by eliminating the unreachable states from start state. In this
example A represents {q0}, B represents {q0, q1} and C represents {q0, q2}.

δ a b
→A B A
B B C
C
B A
Step 7: Constructing the final state transition diagram as shown below
b​ a

start

b
Theorem 3 If DFSA D = (QD, Σ , δD, q0D, FD) is constructed from NDFA N = (QN , Σ , δN , q0N , FN ) by using
the subset construction method, then prove that L(D)=L(N).
Proof. This can be proved by the mathematical induction method.
Basis: Let length of string —W— = 0, i.e input string ϵ, then the extended transition function δˆ for
DFSA δˆD(q0, ϵ) and NFSA δˆN ({q0}, ϵ) will be same i.e. q0.
Induction: Let W = xα where α is the last symbol of the string and x is the remaining string of W. If the
DFSA has the set of states constructed from the NDFSA states by using subset construction method
then δˆD({q0}, x) and δˆN ({q0}, x) will give the same output i.e {p1, p2, p3 pk}
Hence by the Definition of δˆ for NDFSA
δˆN (q0, W ) = Sk​ δN (pi, α)

The subset construction on the other hand

δD({p1, p2, p3.....pk}, α) = Sk​ δN (pi, α) (Equation 1)
That means it is fact that δˆD({q0}, x) = {p1, p2, p3​ pk}, then extended transition function to DFSA is
δˆD({q0}, W ) = δD(δˆD({q0}, x), α) = δD({p1, p2, p3.....pk}, α) = Sk​ δN (pi, α) (Equation 2)
From the Equation 1 and Equation 2, we proved that language is accepted by DFSA is same as the language is
accepted by NDFSA i.e. L(D) = L(N).
Theorem 4 A Language L is regular and accepted by some DFSA iff L is accepted by some NDFSA.
Proof. Let D = (Q, Σ, δD, q0, F ) be a DFSA and N = (Q, Σ, δN , q0, F ) be an equivalent NDFSA,
where the transitions of NDFSA can be obtain from the transitions DFSA as follows

If δD(q, a) = p, then δN (q, a) = {p}

That means, the extended transition function of both finite automata on the input string W should
produce the equivalent states as shown bellow
If δˆD(q, W ) = p, then δˆN (q, W ) = {p}

Hence from this discussion we conclude that the behavior of each state produced by DFSA and
NDFSA must be same on the input string W , then we say that, the language L is accepted by DFSA is
also accepted by NDFSA.

A Bad Case for subset construction Method

From previous discussion on subset construction method, DFSA will have 2n states, when NDFSA is
converted into DFSA by using the subset construction method, need to compute the transition functions
over the input alphabet
n
D on each state of DFSA. Hence the time complexity to convert from NDFSA to DFSA is ⃝(∈ ∗2 ). Since
the time complexity is exponential, and is high expensive computation to convert. To avoid this problem we use
method called as Lazy Evaluation Method where the states of DFSA QD will be keep on updating
whenever new state is appeared while constructing the transition function from the start state of NFSA
instead of computing all possible subset.

Lazy Evaluation Method

1.​Identify the Input Alphabet of DFSA. If Σ​ is the input alphabet of NFSA, then the Σ​ will be the input
alphabet of DFSA where Σ​ =​ .​ N​ D

D
2.​Identify the start state of DFSA. If {q0} is the start state of NFSA, then {q0} will be the start state
of DFSA and add this state to set QD.
3.​Identify states of DFSA: Construct the transition function from the start state of DFSA and update
set QD if any if any new state is identified in the transition function which is not there in set QD.
This step has to be repeated until the no more states of DFSA are identified or until the states of
DFSA are repeated.
4.​Construct the final transition table and state transition diagram with final states.
Example 56 Obtain the equivalent DFSA from the following NDFSA (ending with ab).
a,b

start
Step 1: Identify the input alphabet of DFSA. Here the Input alphabet on DFSA Σ = {a, b} because the
input alphabet of the NDFSA are a,b.
Step 2: Identifying the start state of DFSA. The start state of DFSA is {q0} because the start state of NDFSA is
q0. The set of states Q = {q0}
Step 3: Constructing the transition functions for the states of DFSA as shown below.
δ(q0, a) = {q0, q1} & δ(q0, b) = {q0} (Q = {{q0}, {q0, q1}})

δ({q0, q1}, a) = δ(q0, a) ∪ δ(q1, a) = {q0, q1} ∪ {ϕ} = {q0, q1} (Q = {{q0}, {q0, q1}})

δ({q0, q1}, b) = δ(q0, b) ∪ δ(q1, b) = {q0} ∪ {q2} = {q0, q2} (Q = {{q0}, {q0, q1}, {q0, q2}})
 δ({q0, q2}, a) = δ(q0, a) ∪ δ(q2, a) = {q0, q1} ∪ {ϕ} = {q0, q1} (Q = {{q0}, {q0, q1}, {q0, q2}})

δ({q0, q2}, b) = δ(q0, b) ∪ δ(q2, b) = {q0} ∪ {ϕ} = {q0} (Q = {{q0}, {q0, q1}, {q0, q2}})
Step 4: Constructing the transition table, A represents {q0}, B represents {q0, q1} and C represents {q0, q2}.

δ a b
→A B A
B B C
C
B A
Step 5: Constructing the transition diagram as shown below

b​ a

start

b
Example 57 Obtain the equivalent DFSA from the following NDFSA and analyze the language
accepted by finite automata.

start
1

Solution: δ 0 1
→ {p} {p} {q}
{q} ϕ {r}
{r}
{p, r} {q}

{p, r}
{p, r} {q}
A
=
{
p
}
B
=
{
q
}
C
=
{
r p
} ,
D r
= }
{

start
1
Example 58 Obtain the equivalent DFSA from the following
NDFSA.
0,1​ 0,1

start
Solution:

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

{q0, q2}
{q0, q1, q2} {q0, q2}

{q0, q1, q2}

{q0, q1, q2} {q0, q2}

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

start
1

Example 59 Obtain the equivalent DFSA from the following NDFSA.

a,b

start

Solution: δ a b
→ {q0} {q0} {q0, q1}
{q0, q1} q0 {q0, q1, q2}

{q0, q1, q2}

{q0} {q0, q1, q2}

A
=
{
q
0
}
B
=
{ q
q 0
0 ,
, q
q 1
1 ,
} q
C 2

= }
{

a​ b

start

a
Example 60 Obtain the equivalent DFSA from the following NDFSA.
0​ 1

start

Solution: δ 0 1
→ {q0} {q0, q1} {q1}

{q0, q1}
{q0, q1, q2} {q1, q2}
{q1}
{q2} {q2}

{q0, q1, q2}

{q0, q1, q2} {q1, q2}

{q1, q2}
ϕ {q2}
{q2} ϕ {q2}

A
=
{
q
0
}
B
=
{
q
0
,
q
1
}
C
=
{
q
1
}
D
=
{
q q
0 1
, ,
q q
1 2
, }
q F
2
=
} {
E q
= 2
{ }

start

OR
Eliminate the trap state q2, then
 δ 0 1
→ {q0} {q0, q1} {q1}

{q0, q1}
{q0, q1} {q1}
{q1}
ϕ ϕ

A = {q0}
B = {q0, q1}
C = {q1}

start

Example 61 Obtain the equivalent DFSA from the following NDFSA.

1

start
0​ 1

Solution: δ 0 1
→ {q0} {q1} {ϕ}
{q1}
{q0} {q1, q2}

{q1, q2}
ϕ {q1, q2}

A
=
{
q
0
}
B
=
{
q q
1 1
} ,
C q
= 2

{ }

start
0

Example 62 Obtain the equivalent DFSA from the following NDFSA.

 0​ 1​ 2

start

1,2

Solution: δ 0 1 2
→ {q0} {q0, q1, q2} {q1, q2} {q2}

{q0, q1, q2}

{q0, q1, q2} {q1, q2} {q2}

{q1, q2}
ϕ {q1, q2} {q2}
{q2}
ϕ ϕ {q2}

A
=
{
q
0
}
B
=
{
q
0
,
q
1
,
q
2
}
C
=
{
q
1
,
q
2
}
D
= 2
{ }
q

start​ 2

1.4.7​ Review Questions

1.​Why do we need to obtain DFA from NFA?
2.​List the process of eliminating the ϵ transitions

1.4.8​ Exercises
1.​Obtain an equivalent DFSA from following NDFSA
 δ 0 1
→p {p, r} {q}
q {r, s} {p}
{r}
{p, s} {r}
{s}
{q, r} ϕ

2.​For each of the following languages, construct an NDFSA, that accepts the language over the
alphabet {0, 1} and also obtain an equivalent DFSA.
(a)​ L = {w : w ends with 10} with three states.
(b)​L = {w : w contains the substring 11001}.
(c)​ L = {w : w has length at least 2 and does not end with 10}.
(d)​L = {w : w begins with 1 or ends with 0}.
(e)​L = {w : w contains the substring 1011} with five states.
(f)​ L = {w : w contains an odd number of 1s or exactly two 0s} with six states.
3.​Obtain an equivalent DFSA from following NDFSA

δ 0 1
→p {p, q} {p}
q {r, s} {t}
r {p, r} {t}
{s}
ϕ ϕ
{t}
ϕ ϕ

4.​Convert the following NFA to an equivalent DFA

start

b
1.5​ Applications of Theory of Computation
The applications of theory of computation used in day to day computation domain and other activities.
Wherever there is a computation, the application of theory of computation is used. We listed below
some of the application that are considered:
1.​Developing Language between person and machine: The theory of computation enables
communication and computation between machine - machine, person - person and
person-machine. Without these non of the today’s application of computing domain could exist.
Example: Communication protocols in network, HTML etc.
2.​Implementation of Modern Programming Language: The Context free languages(CFL) and
Context free grammar(CFG) are used in designing and implementing the modern programming
language, because CFG are used to design the language syntax and semantic techniques. Example:
Compilers
3.​Natural Language Processing: The people use the natural language (english) to communicate
with person and the system applications. These system application has to process our natural
language and do the computation. Best example is google search engine.
4.​Developing hardware system: Parity checker, vending machine, communication protocols and
security devices can be designed and described by finite state automata.
5.​Interactive Video games: Many interactive video games uses the the finite state automata to
describe the role of each state in the game.
6.​Computer Security: Security is perhaps the most important property of many computer systems.
The undecidability results of computation show that there cannot exist a general-purpose method
for automatically verifying arbitrary security properties of programs.
7.​Developing Artificial Intelligent system: Artificial intelligence programs solve problems in
domains ranging from medical diagnosis to factory scheduling. Various logical frameworks have
been proposed for representing and reasoning with the knowledge that such programs exploit.

1.5.1​ An Application: Text Search

The important application of finite automata is to carry out the text search computation. If we
considered the problem of deciding whether a sequence of bits ends with 01 is actually an excellent
example for several real problems that appear in the applications such as Web search and extraction of
information from text.
•​Finding Strings in Text: A common problem in the era of the Web and other on line text
repositories is the following Given a set of words and all documents that contain one or all of
those words. A search engine is a popular example of this process. The searching of text in a
string computing model or abstract model can be designed by using finite automata either by
constructing deterministic or non-deterministic finite automata.
•​Non-deterministic Finite Automata for Text Search: Constructing a Deterministic Finite
Automata for searching text is very complex. That is why the Non-deterministic finite automata
will be constructed so that it can be converted in the DFA later. Suppose we are given a set of
words which we shall call the keywords and we want to find occurrences of any of these words. In
applications such as these a useful way to proceed is to design a non-deterministic finite
automaton which signals by entering an accepting state that it has seen one of the keywords. The
text of a document is fed one character at a time to this NFA which then recognizes occurrences of
the keywords in this text. There is a simple form to an NFA that recognizes a set of keywords.
1.5.2​ Review Questions
1.​List the applications of finite automata
2.​Describe finding strings in text
3.​Describe NFA for text search
1.6​ Non-deterministic Finite Automata with ϵ Transition (ϵ- NFA)
The Non-deterministic finite sate automata with ϵ transitions called ϵ − NDFSA where Finite state
automata will have transitions on ϵ i.e. without any input symbol. The moving from one state to another
state without consuming any input symbol called as ϵ-transitions. The NDFSA with ϵ - Transition is
called as ϵ − NDFSA.

1.6.1​ Definition and uses of ϵ - Transition

The Finite state control moves from one state to another state without any input symbol ϵ is called as ϵ
-Transition. The ϵ -Transition will indicates that optional transition wherever and whenever it requires.
For example if you consider the finite state automata to accept the decimal numbers with an optional +
(Positive) or - (Negative)sign and dot(.), then we need to look for the ϵ − NDFSA itself. Because it
gives the optional transition as shown below.

start

If input string is 908.0002, then previous finite automata i.e ϵ − NDFSA will accept this string. This
input string represents by default positive decimal numbers even though the + sign is not there, in that
case the transition will take from q0 to q1 without any input symbol ϵ. Hence the ϵ − NDFSA can have
the transitions without any input symbol.

1.6.2​ Definition of ϵ- NFA

The ϵ - Non-deterministic finite state automata is same as Non-Deterministic finite state automata and
is extended version of NFSA, but only difference in the transitions in which the ϵ-NDFSA has ϵ
transitions. The ϵ-NDFSA can be defined as follows.
N = (Q, Σ, δ, q0, F )

1.6.3​ Formal Notation of an ϵ- NDFSA

As we seen in the previous section, the ϵ- NDFSA is same as NFSA with ϵ transition. So any number of
states Q can have ϵ transitions. If you consider the previous example which accepts the decimal
numbers in which the ϵ − NDFSA is represented as
EN = ({q0, q1, q2, q3, q4, q5, q6}, {., +, −, 0, 1, 2, ...9}, δ, q0, {q6})
The transition table can be written as

δ ϵ +,- . 0,1,2...9
q0 {q1} {q1} ϕ ϕ
q1 ϕ ϕ {q2} {q1, q2}
q2 ϕ ϕ ϕ {q3}
q3 {q5} ϕ ϕ {q3}
q4 ϕ ϕ {q3} ϕ
q5 ϕ ϕ ϕ ϕ
1.6.4​ Epsilon-Closures (ϵ - closure or ecl())
Informally ϵ − closure of state q can be defined as all transitions out from q that are labeled ϵ. Formally
we define the ϵ − closure of state q is ecl(q) recursively. That means ecl(q) is the set of all other states
which are reachable from state q on ϵ − transitions only.
Basis: State q is in ecl(q), that means ecl(q)=q itself.
Induction: If state p is in ecl(q), and if there is transition from state p to state r with ϵ symbol, then
state r is also in ecl(q). that means ecl(q) = {q, p, r}.
Example 63 If you consider the previous example which accepts the decimal numbers with +, - sign. In that
ecl(q0) = {q0, q1}
ecl(q1) = {q1}
ecl(q2) = {q2}
ecl(q3) = {q3}
ecl(q4) = {q4}
ecl(q5) = {q5, q6}
ecl(q6) = {q6}
Example 64 Find the ECLOSURE of each state of following ϵ − NDFSA.

start

ecl(q0) = {q0, q1, q2, q3, q4}

ecl(q1) = {q1, q2, q3}
ecl(q2) = {q2, q3}
ecl(q3) = {q3}
ecl(q4) = {q4}
ecl(q5) = {q5, q6}
ecl(q6) = {q6}

1.6.5​ Extended Transition Function to ϵ- NDFSA

The extended transition function for ϵ − NDFSA decides whether the input string will be accepted or
rejected by scanning the entire input string from left to right. It takes two arguments i.e current state q0
& input string W and produces the output as next Set of state like {p1, p2, p3...pk} recursively. Then
ECLOSURE({p1, p2, p3...pk}) = ECLOSURE(p1) ∪ ECLOSURE(p2) ∪ ECLOSURE(p3) ∪ .... ∪
ECLOSURE(pk) = {r1, r2, r3 rk} will be the
next state in which any one of the state ∈ F then input string will be accepted, otherwise string will be
rejected. We will prove this by using mathematical induction method to accept the input string. The
input string will be divided into two part W = xα where x is the remaining input string and α represents
the last input symbol of the string. The remaining input string x will keep on dividing into two part i.e x
= xα recursively until it equals to ϵ where it reach to the base condition.
Basis: δˆ(q0, ϵ) = ECLOSURE(q0).
Induction: The input string will be divided into two part W = xα where x is the remaining input string
and α represents the last input symbol. And the remaining input string x will keep on dividing into two
part i.e x = xα recursively until it equals to ϵ.
δˆ(q0, W ) = δˆ(q0, xα)
δˆ(q0, xα) = ECLOSURE(δ(δˆ(q0, x), α))

1.​Let δˆ(q0, x) = {p1, p2, p3, ....pk} then δ({p1, p2, p3, ....pk}, α) = δ(p1, α) ∪ δ(p2, α) ∪ δ(p3, α)​ ∪ δ(pi, α)
 2.​Let δ(p1, α)∪δ(p2, α)∪δ(p3, α)......δ(pk, α) = {r1, r2, r3....ri}. Hence the ϵ−NDFSA will be ECLOSURE({r1, r2,
r3​ ri} =
ECLOSURE(r1) ∪ ECLOSURE(r2) ∪ ECLOSURE(r3) ∪​∪ ECLOSURE(rk)
3. ˆ
​ That means δ (q0, W ) = Sm ECLOSURE(rk).

Example 65 Let us consider the ϵ-NFSA with decimal number example which accepts the decimal numbers with
+,- sign, check whether the input string 5.6 will be accepted or rejected.
Basis: δˆ(q0, ϵ) = ECLOSURE(q0) = {q0, q1}.
Induction:
1.​δˆ(q0, W ) = δˆ(q0, 5.6)
2.​δˆ(q0, 5.6) = δ(δˆ(q0, 5.), 6)
3.​δ(δˆ(q0, 5.), 6) = δ(δ(δˆ(q0, 5), .), 6)
4.​δ(δ(δˆ(q0, 5), .), 6) = δ(δ(δ(δˆ(q0, ϵ), 5), .), 6)
5.​δ(δ(δ(δˆ(q0, ϵ), 5), .), 6) = δ(δ(δ({q0, q1}, 5), .), 6)
6.​δ(δ(δ({q0, q1}, 5), .), 6) = δ(δ({q1, q4}, .), 6) where (δEN (q0, 5) ∪ δEN (q1, 5) = ϕ ∪ {q1, q4}).
7.​δ(δ({q1, q4}, .), 6) = δ({q2, q3}, 6) where (δEN (q1, .) ∪ δEN (q4, .) = {q2} ∪ {q3}).
8.​δ({q2, q3}, 6) = {q3, q5}
9.​Hence ECLOSURE({q3, q5}) = ECLOSURE(q3) ∪ ECLOSURE(q5) = {q3} ∪ {q5, q6} = {q3, q5, q6}. Since
q6 ∈ F hence the string will be accepted.

1.6.6​ Language of ϵ- NDFSA

The Language of ϵ-Non-Deterministic Finite State Automata EN = (Q, Σ, δ, q0, F ) is denoted as L(EN ) and can
be defined as
L(EN ) = {W | W ∈ Σ∗ s.t δˆ(q0, W ) ∈ F }

The language of ϵ-NDFSA EN , is the set of string over Σ which takes input string from the start state & process
it and produces the output as next state which belongs to final state.

1.6.7​ Review Questions

1.​List the difference between DFA, NFA, ϵ − NFA
2.​Define ϵ − NFA?
3.​Define Language of ϵ − NFA?
4.​Define E-closure function
1.6.8​ Equivalent ϵ- NDFSA and DFSA
The equivalent DFSA need to be obtain from ϵ − NDFSA due to all computers are deterministic by
using the lazy evaluation method with ϵ transitions. ϵ − NDFSA is very easy to construct than the
DFSA, Since all computers are the Deterministic the ϵ − NDFSA has to be converted into DFSA, need
to map from ϵ − NDFA(EN =
(Q1.
EN , Σ​ , δEN , q0EN , FEN )) to DFSA (D = (QD, Σ , δD, q0D, FD)).
​ Identify the Input Alphabet of is the input alphabet of ϵ − will be
DFSA. If Σ NDFSA, then the Σ
the input alphabet of DFSA where Σ = ΣEN .​ D

2.​Identify the start state of DFSA. If q0 is the start state of ϵ − NDFSA, then ecl(q0) will be the start
state of DFSA and add this state to set QD.
3.​Identify state of DFSA: Construct the transition function from the start state of DFSA i.e δD(q0, α)
= ecl(δEN (q0, α) & keep on updating the QD if any new state is identified in the transition which is
not in QD. Let {q0, q1, q2....qk} is state in DFSA, then the transitions from this state on input
alphabet α i.e. δD({q0, q1, q2 qk}, α) is computed as shown below
– δEN ({q0, q1, q2....qk}, α) = {p1, p2, p3​pk}
– then ecl({p1, p2, p3​ pk}) will be the next state.
This step has to be repeated until no more new states of DFSA are identified.
4.​If {q0, q1, q2​qk} is the state of DFSA & if this set contains the at least one final state of ϵ − NDFSA, then
{q0, q1, q2​ qk} will be final state of DFSA and Construct the transition table and transition diagram.
Example 66 Obtain the DFSA from following ϵ − NDFSA

start

Step 1: Identifying the input of DFSA. Here the input alphabet Σ N of ϵ−NDFSA is {+, −, ., 0, 1, 2, 3,​
alphabet Σ will be the input alphabet 9}
of DFSA.

Step 2: Identifying the start state of DFSA. The start state of ϵ − NDFSA is q0, then the ecl(q0) = {q0, q1}
will be the start of DFSA. The states of DFSA will be Q = {{q0, q1}}.
Step 3: Identifying the states of DFSA and constructing the transition function for those states by using the
ϵ − NDFSA.

For the state {q0, q1}

•​δD({q0, q1}, +) = δEN (q0, +) ∪ δEN (q1, +) = {q1} ∪ {ϕ} = {q1} = ecl(q1) = {q1} (Q = {{q0, q1}, {q1}})
•​δD({q0, q1}, −) = δEN (q0, −) ∪ δEN (q1, −) = {q1} ∪ {ϕ} = {q1} = ecl(q1) = {q1} (Q = {{q0, q1}, {q1}})

•​δD({q0, q1}, .) = δEN (q0, .) ∪ δEN (q1, .) = {ϕ} ∪ {q2} = {q2} = ecl(q2) = {q2} (Q = {{q0, q1}, {q1}, {q2}})
•​δD({q0, q1}, 0, 1, 2, ....9) = δEN (q0, 0, 1, 2, ....9)∪δEN (q1, 0, 1, 2,​ 9) = {ϕ}∪{q1, q4} = {q1, q4} = ecl({q1,
q4}) =
{q1, q4} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

For the state {q1}

•​δD({q1}, +) = δEN (q1, +) = ϕ (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

•​δD({q1}, −) = δEN (q1, −) = ϕ (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

•​δD({q1}, .) = δEN (q1, .) = {q2} = ecl(q2) = {q2} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

•​δD({q1}, 0...9) = δEN (q1, 0​ 9) = {q1, q4} = ecl({q1, q4}) = {q1, q4} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

For the state {q2}

•​δD({q2}, +) = δEN (q2, +) = ϕ (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

•​δD({q2}, −) = δEN (q2, −) = ϕ (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

•​δD({q2}, .) = δEN (q2, .) = {ϕ} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}})

•​δD({q2}, 0...9) = δEN (q2, 0​ 9) = {q3} = ecl(q3) = {q3} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}})

For the state {q1, q4}

•​δD({q1, q4}, +) = δEN (q1, +) ∪ δEN (q4, +) = ϕ
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}})

•​δD({q1, q4}, −) = δEN (q1, −) ∪ δEN (q4, −) = ϕ

(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}})

•​ δD({q1, q4}, .) = δEN (q1, .) ∪ δEN (q4, .) = {q2} ∪ {q3} = {q2, q3}
ecl({q2, q3}) = {q2, q3} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}})

•​ δD({q1, q4}, 0...9) = δEN (q1, 0...9) ∪ δEN (q4, 0​ 9) = {q1, q4} ∪ {ϕ}
ecl({q1, q4}) = {q1, q4} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}})

For the state {q3}

•​δD({q3}, +) = δEN (q3, +) = ϕ
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}})

•​δD({q3}, −) = δEN (q3, −) = ϕ

 (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}})

•​ δD({q3}, .) = δEN (q3, .) = {ϕ}

(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}})
•​ δD({q3}, 0...9) = δEN (q3, 0...9) = {q5} = ecl(q5) = {q5,
q6}
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5,
q6}})

For the state {q2, q3}

•​δD({q2, q3}, +) = δEN (q2, +) ∪ δEN (q3, +) = ϕ
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}})

•​δD({q2, q3}, −) = δEN (q2, −) ∪ δEN (q3, −) = ϕ

(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}})

•​δD({q2, q3}, .) = δEN (q2, .) ∪ δEN (q3, .) = ϕ

(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}})

•​ δD({q2, q3}, 0, 1, 2, ....9) = δEN (q2, 0, 1, 2, ....9) ∪ δEN (q3, 0, 1, 2,​ 9) = {q3} ∪ {q5} = {q3, q5}
ecl({q3, q5}) = {q3, q5, q6} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

For the state {q5, q6}

•​ δD({q5, q6}, +) = δEN (q5, +) ∪ δEN (q6, +) = {ϕ}
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

•​ δD({q5, q6}, −) = δEN (q5, −) ∪ δEN (q6, −) = {ϕ}

(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

•​ δD({q5, q6}, .) = δEN (q5, .) ∪ δEN (q6, .) = {ϕ}

(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

•​ δD({q5, q6}, 0, 1, 2, ....9) = δEN (q5, 0, 1, 2, ....9) ∪ δEN (q6, 0, 1, 2,​ 9) = {q5} ∪ {ϕ} = {q5}
ecl(q5) = {q5, q6} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

For the state {q5, q6}

•​ δD({q3, q5, q6}, +) = δEN (q3, +) ∪ δEN (q5, +) ∪ δEN (q6, +) = {ϕ}
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

•​ δD({q3, q5, q6}, +) = δEN (q3, −) ∪ δEN (q5, −) ∪ δEN (q6, −) = {ϕ}
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

•​ δD({q3, q5, q6}, .) = δEN (q3, .) ∪ δEN (q5, .) ∪ δEN (q6, .) = {ϕ}
(Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

•​ δD({q3, q5, q6}, 0, 1, 2, ....9) = δEN (q3, 0, 1, 2, ....9) ∪ δEN (q5, 0, 1, 2, ....9) ∪ δEN (q6, 0, 1, 2,​ 9) = {q5}
 ∪ {q5} ∪
{ϕ} = {q5}
ecl(q5) = {q5, q6} (Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}})

The each states of DFSA Q = {{q0, q1}, {q1}, {q2}, {q1, q4}, {q3}, {q2, q3}, {q5, q6}, {q3, q5, q6}} will
be represented as Q = {A, B, C, D, E, F, G, H} respectively.
The final transition table is as shown below
 δ + - . 0...9
→A B B ϕ D
B ϕ ϕ C D
C ϕ ϕ ϕ E
D ϕ ϕ F D
E ϕ ϕ ϕ G
F ϕ ϕ ϕ H
G
ϕ ϕ ϕ G
H
ϕ ϕ ϕ G
The corresponding transition diagram is
0,1,...9

start

0,1,...9

Theorem 5 A language L is accepted by some ϵ − NDFSA iff L is accepted by some DFSA

Proof. Let E = (QE, Σ, δE, q0 , FE) be an ϵ − NDFSA and D = (QD, Σ, δD, q0 , FD) be an equivalent DFSA.
This theorem will be proved by extended transition functions of ϵ − NDFSA and DFSA. So we need to
prove that
δˆE (q0, W ) = δˆD(q0, W )
Basis: We know that the basis of extended transition function to ϵ − NDFSA is
δˆE (q0, ϵ) = ecl(q0) − − − −1
While converting from ϵ − NDFSA to DFSA, the start state of DFSA will be ECOSURE(q0E ). So
δˆD(q0D , ϵ) = δˆD(ecl(q0E ), ϵ) = ecl(q0E ) − −
− 2 From 1 and 2 we proved that δˆE (q0, ϵ) = δˆD(q0, ϵ)
Induction: Let W = xα and need to prove that
δˆE (q0, xα) = δˆD(q0, xα)
We know that from the extended transition function of ϵ − NDFSA
δˆE (q0, xα) = δE(δˆE (q0E , x), α)
= δE({p1, p2, ....pk}, α) = ecl(∪k {q1, q2,​qk}
= {r1, r2, r3​ rk} − − − − − −3
When we convert ϵ − NDFSA into DFSA, & to process the input string by using extended transition
function DFSA is given as
δˆD(q0, xα) = δD(δˆD(q0D , x), α)
 = δD({p1, p2,​ pk}, α) = δ(pi, α)
ecl(∪k

= {r1, r2, r3​ rk} − − − − − −4

From the equation 3 and 4, we proved that δˆE (q0, xα) = δˆD(q0, xα). So the language is accepted by
some ϵ−NDFSA
will also be accepted by DFSA

Example 67 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA

a​ b​ c

start

Solution: ecl(q0) =
{q0, q1, q2}
ecl(q1) =
{q1, q2}
ecl(q2) =
Transition Table: {q2}

δ a b c

{q0, q1, q2}

→ {q0, q1, q2} {q1, q2} {q2}

{q1, q2}
ϕ {q1, q2} {q2}
{q2}
ϕ ϕ {q2}

A = {q0, q1,
q2}
B = {q1,
q2}
C = {q2}

a​ b​ c
 start

Example 68 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA

start

ϵ,b
Solution:

Transition Table:
 ecl(p) = {p, q, r} ecl(q) = {q} ecl(r) = {p, q, r}

δ a b

{p, q, r}
→ {p, q, r} {p, q, r}

A = {p, q, r}
a,b

start

Example 69 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA
a​ a

start

Solution:

Transition Table:
 ecl(p) = {p}
ecl(q) = {q}
ecl(r) = {p, q, r}

δ a b c
→ {p} {p} {q} {p, q, r}
{q} {q} {p, q, r} ϕ

{p, q, r}
{p, q, r} {p, q, r} {p}

start
 A = {p}
B = {q}
C = {p, q, r}

a​ a
a,b

c
Example 70 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA
a​ a​ a

start

Solution:

Transition Table:
 ecl(p) = {p}
ecl(q) = {p, q}
ecl(r) = {p, q, r}

δ a b c
→ {p} {p} {p, q} {p, q, r}
{p, q} {p, q} {p, q, r} {p, q, r}

{p, q, r}
{p, q, r} {p, q, r} {p}

start
 A = {p}
B = {p, q}
C = {p, q, r}

a​ a
 a,b

Example 71 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA
1

start
0​ 1

Solution:

Transition Table:
ecl(q0) = {q0}
ecl(q1) = {q1, q2}
ecl(q2) = {q2}

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

{q1, q2}
{q2} {q1, q2}
{q2} ϕ {q1, q2}
A = {q0}
B = {q1, q2}
C = {q2}

start

Example 72 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA
c
tart
Solution:

Transition Table:

ecl(p) = {p, q, r} ecl(q) = {q}

ecl(r) = {r}

δ a b c

{p, q, r}
{p, q, r} {q, r} {p, q, r}

{q, r}
{p, q, r} {r} {p, q, r}
{r}
ϕ ϕ ϕ
A = {p, q, r}
B = {q, r}
C = {r}
a,c

start
a,c

Example 73 Computer ECLOSURE of each state and obtain a DFSA from the following ϵ − NDFSA

start

0,1

Solution:

Transition Table:
 ecl(q0) = {q0, q1}
ecl(q1) = {q1}
ecl(q2) = {q2}

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

{q1, q2}
{q0, q1, q2} {q2}

{q0, q1, q2}

{q0, q1, q2} {q2}

A = {q0, q1}
B = {q2}
C = {q1, q2}
D = {q0, q1, q2}

start
1
1.6.9​ Review Questions
1.​Why do we need to obtain DFA from ϵ − NFA?
2.​List the process of eliminating the ϵ transitions

1.6.10​ Exercises
1.​Design an ϵ −NDFSA for the following languages and obtain an equivalent DFSA by computing
ECLOSURE of each state.
(a)​ The set of strings that consist of either 01 repeated one or more times or 010 repeated one or more times.
(b)​The set of string consist of 0 and 1 in which 2nd symbol from right end is 1
(c)​The set of string consist of 0 and 1 in which 2nd symbol from right end & left end is 1.
2.​Compute the ECLOSURE of each state and obtain an equivalent DFSA for the following finite automata
0​ 1

start
3.​Compute the ECLOSURE of each state and obtain an equivalent DFSA for the following finite automata

start