SUBJECT NAME: CS3452-THEORY OF

COMPUTATION
 UNIT I

UNIT I AUTOMATA AND REGULAR EXPRESSIONS

Need for automata theory - Introduction to formal proof – Finite

Automata (FA) – Deterministic Finite Automata (DFA) – Non-
deterministic Finite Automata (NFA) – Equivalence between NFA and
DFA – Finite Automata with Epsilon transitions – Equivalence of NFA
and DFA- Equivalence of NFAs with and without ε-moves- Conversion
of NFA into DFA – Minimization of DFAs.
 INTRODUCTION TO TOC

 Theory of Computation(TOC) is a branch of

computer science and mathematics combined that
"deals with how efficiently problems can be
solved on a model of computation, using an
algorithm".
 It can be of 3 branches
1. Automata Theory
a)Formal Language Theory
2. Computability Theory
3. Complexity Theory
 NEED OF TOC

 Provides strong foundation for abstract areas

in computer science.
 That means “How does a computer is made
to think?”
 Example:
1) Whether a machine will accept a string or
not? (Or)
2) Checking if a string is palindrome or not?
 REAL LIFE APPLICATIONS OF TOC

 CLOUD
 VM
 HADOOP/BIGDATA
 SYMBOLS USED IN TOC

UPPER CASE LOWER CASE SYMBOL NAME

Δ 𝛿 DELTA

Ε ε EPSILON

Ζ ζ ZETA

Ξ ξ XI

Σ σ SIGMA

Γ γ GAMMA

Ω ω OMEGA
 TERMINOLOGIES USED IN TOC
1. Alphabet  It is any finite set of symbols.
Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’,
‘c’, and ‘d’ are symbols.
2. String --> It is a finite sequence of symbols taken from ∑.
Example − ‘cabcad’ is a valid string on the alphabet set ∑ =
{a, b, c, d}
3. Length of a String It is the number of symbols present in a
string. (Denoted by |S|).
Examples −
– If S = ‘cabcad’, |S|= 6
– If |S|= 0, it is called an empty string (Denoted by λ or ε)
 Cont..
4. Prefix Leading symbols of the string.

5. Suffix Trailing symbols of the string.

6. Kleene Star The Kleene star, ∑*, is a unary operator on a set of

symbols or strings, ∑, that gives the infinite set of all possible strings
of all possible lengths over ∑ including λ.

• Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. where ∑p is the set

of all possible strings of length p.

• Example − If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,…..........}

 Cont..
7. Kleene Closure / Plus The set ∑+ is the infinite set of all
possible strings of all possible lengths over ∑ excluding λ.
• Representation − ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪…….
• ∑+ = ∑* − { λ }
• Example − If ∑ = { a, b } , ∑+ = { a, b, aa, ab, ba,
bb,…..............}
8. Language Set of strings of symbol from one alphabet.
Any set of strings over an alphabet’ ∑’.
 INTRODUCTION TO FORMAL PROOF:

FORMAL PROOF:
 Formal proof or Derivation is a finite sequence of sentences
(called well-formed formulas in the case of a formal
language),.
Basic Symbols used :
U – Union, ∩- Conjunction,
ϵ - Empty String, Φ – NULL set ,
7- negation, ‘ – compliment, = > implies
Additive inverse: a+(-a)=0
Multiplicative inverse: a*1/a=1
Universal set U={1,2,3,4,5}
Subset A={1,3}
A’ ={2,4,5}
Absorption law: AU(A ∩B) = A, A∩(AUB) = A
De Morgan’s Law:
1) (AUB)’ =A’ ∩ B’
2) (A∩B)’ = A’ U B’
Double compliment
1) (A’)’ =A
2) A ∩ A’ = Φ
Relation:(Set of Pairs)
 Relation or Binary relation R from set A to B is a subset of AxB
which can be defined as aRb ↔ (a,b) € R ↔ R(a,b).
 A Binary relation R on a single set A is defined as a subset
of AxA.
 For two distinct set, A and B with cardinalities m and n, the
maximum cardinality of the relation R from A to B is mn.
Types of Relation:

1) Empty Relation: A relation R on a set A is called Empty if the

set A is empty set.
2) Full Relation: A binary relation R on a set A and B is called
full if AXB.
3) Reflexive Relation: A relation R on a set A is called reflexive
if (a,a) € R holds for every element a € A .i.e. if set A = {a,b}
then R = {(a,a), (b,b)} is reflexive relation.
4) Irreflexive relation : A relation R on a set A is called reflexive
if no (a,a) € R holds for every element a € A.i.e. if set A = {a,b}
then R = {(a,b), (b,a)} is irreflexive relation.
5) Symmetric Relation: A relation R on a set A is called
symmetric if (b,a) € R holds when (a,b) € R.i.e. The relation
R={(4,5),(5,4),(6,5),(5,6)} on set A={4,5,6} is symmetric.
 6) AntiSymmetric Relation: A relation R on a set A is
called antisymmetric if (a,b)€ R and (b,a) € R then a = b is
called antisymmetric. i.e. The relation R = {(a,b)→ R|a ≤ b}
is anti-symmetric since a ≤ b and b ≤ a implies a = b.
7) Transitive Relation: A relation R on a set A is called transitive if
(a,b) € R and (b,c) € R then (a,c) € R for all a,b,c € A.
i.e. Relation R={(1,2),(2,3),(1,3)} on set A={1,2,3} is transitive.
8) Equivalence Relation: A relation is an Equivalence Relation if
it is reflexive, symmetric, and transitive. i.e. relation R={(1,1),(2,2),
(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)} on set
A={1,2,3} is equivalence relation as it is reflexive, symmetric, and
transitive.
9) Asymmetric relation: Asymmetric relation is opposite of
symmetric relation. A relation R on a set A is called asymmetric if
no (b,a) € R when (a,b) € R.
ADDITIONAL FORMS OF PROOF:

1) Proof of sets – A set is a collection of elements.

2) Proof by contradiction - Determines the truth of a statement by
assuming the proposition is false, then working to show its
falsity until the result of that assumption is a contradiction.
3) Proof by counter example - It is a way of showing that a given
statement cannot possibly be correct by showing an instance
that contradicts a universal statement.
INDUCTIVE PROOFS:
 A proof by induction is just like an ordinary proof in
which every step must be justified.
 It allows you to prove a statement about an arbitrary number n
by first proving it is true when n is 1 and then assuming it is true
for n=k and showing it is true for n=k+1.
 INTRODUCTION TO AUTOMATA

 The term "Automata" is derived from the Greek

word "αὐτόματα" which means "self-acting".
 An automaton (Automata in plural) is an abstract
self- propelled computing device which follows a
predetermined sequence of operations automatically.
 An automaton with a finite number of states is called a
“Finite Automata (FA) or Finite State Machine
(FSM)”.
 Pattern searching in websites.
 ADVANTAGES OF FA

 Implement a system with a fixed set of resources.

 Implement a system within a h/w circuit.
FORMAL DEFINITION OF A FINITE AUTOMATA

A Finite Automata is a collection of a 5-tuples defined as

M= (Q, ∑, δ, q0, F), where
• Q is a finite set of states, which is non-empty.
• ∑ is a finite set of symbols, called the input
alphabet of the automaton.
• δ is the transition function/mapping function
(i.e) next state can be determined.

processed (q0 ∈ Q).

• q0 is the initial state from where any input is

• F is a set of final state/states of Q (F ⊆ Q).

 MODEL OF FA
1. INPUT TAPE  Linear tape having some number
of cells. Each i/p symbol is placed in each cell.
2. FINITE CONTROL It decides the next state on
receiving particular i/p from i/p tape. The tape
reader reads the cells 1-by-1 from left to right & at
a time only one i/p symbol is read.

a b a b a b
 TYPES OF AUTOMATA

1. Deterministic Finite Automata(DFA):

Each move in this automata is
determined on ‘current input & current state’.

2. Non-Deterministic Finite Automata(NFA):

It has the power to be in several state
at once.
ACCEPTANCE OF STRINGS & LANGUAGE IN FA:
 There are 2 preferred notations for describing
automata.
1. Transition Diagram
2. Transition

Table Start State S0

Represents the state S1

Final States Sn
 CONT..

1. Transition Diagram/Graph:
It can be defined as collection of
i) Finite set of states K.
ii) Finite set of symbols Σ.

iv) A set F ⊆ K of final states.

iii) A non-empty set S of K. It is called ‘Start State’.

v) A transition fn. K X A->K with K as state & A

as i/p from Σ*.
 CONT..

2. Transition Table:
It is a tabular representation of finite automata.

Problems:
1) Design FA which accepts only string ‘101’ over
the input ={0,1}.
Note: For this problem we have perform both ‘Transition
Diagram & Transition Table’.
 CONT..
Transition Diagram/Graph:

start S0 S1 S2 S3

1 0 1 Final State
Transition Table:
I/P
States
0 1
S0 - S1
S1 S2 -
S2 - S3
S3 - -
2) Design FA of transition graph which accept
the input “aabb”. Analyze the correct
sequence given below
A) q0 q1 q2 q3 q4

a a b b
B) q1 q2 q3 q4 q5

a a b
C) q1 q1 q1 q1 q1

a a b b
2) Design FA of transition graph which accept
the input “aabb”.
Answer:
A) q0 q1 q2 q3 q4

a a b b
B) q1 q2 q3 q4 q5

a a b
C) q1 q1 q1 q1 q1

a a b b
3) Given M= (Q, ∑, δ, q0, F) , Q={q0,q1,q2,q3},
∑={0,1} , F={q0}. Check whether the i/P string
“110101” is accepted by FA (or) not. The transition dig
is
Sol:

I/P
States 0 1
q0 q2 q1

q1 q3 q0

q2 q0 q3

q3 q1 q2
cont..

The given input string is 110101, for that we have to

check

1 1 0 1 0 1

q0 q1 q0 q2 q3 q1 q0

Therefore, 110101 is in L(M).

 DETERMINISTIC FINITE AUTOMATA(DFA)
 There is only one path for a specific input from current
state to next state.
 It is defined as a collection of 5 tuples defined as
M= (Q, ∑, δ, q0, F), where
Q  Finite set of states.

q0  Start State/ initial state (i.e.) (q0 ∈ Q).

∑  Finite set of input symbols

F  Final state/states (i.e.) (F ⊆ Q).

δ Transition fn./Mapping fn. (i.e.) 2 parameters are
passed to this transition. 1 is current state and other is i/p
symbol. The transition fn. returns a state is called ‘next
state’.
1) Design a FA which checks whether the given
binary no. is even.
Sol:
Binary no. is made up of 0’s & 1’s,it ends with ‘0’ it
is always even and ends with ‘1’ it is always odd.
EVEN NO: 01000 , ODD NO: 1011
Note : While designing FA, will assume one start
state, one state ending in 0 & other state ending with
1. We make that the state for 0 is final state.

Let us assume S1 for all 1’s and S2 for all 0’s.

EVEN NO: 01000
01000 => 0S21000
01S1000
010S200
0100S20
01000S2. (Final State)
ODD NO: 1011
1011=> 1S1011
10S211
101S11
1011S1. (Non-Final State)
PROBLEMS:
1) Design a DFA to accept the string '1011' over
the input {0,1}.

2) Write a DFA to accept the

language W={W:|W| Mod
3=0}
NON-DETERMINISTIC FINITE AUTOMATA(NDFA/NFA):

 NFA refers to “Non- Deterministic Finite Automaton.”

 A Finite Automata(FA) is said to be non deterministic, if there
is more than one possible transition from one state on the same
input symbol.
 It is exactly reverse of DFA.

Note: NFA shows from q0 state for i/p ‘0’ , there are two next states
are q0 & q1.
NFA/NDFA DEFINITION:
An NDFA can be represented by a 5-tuples
M=(Q, ∑, δ, q0, F) where
Q Finite set of states.
∑  Finite set of symbols called the alphabets.
δ
 Transition function where δ: Q × ∑ → 2Q
(Here the power set of Q (2Q) has been taken because in case
of NDFA, from a state, transition can occur to any

q0 Initial state from where any input is processed (q0 ∈ Q).

combination of Q states)

F set of final state/states of Q (F ⊆ Q).

Example
Let a non-deterministic finite automaton be
Q = {a, b, c}
∑ = {0, 1}
q0 = {a}
F = {c}
The transition function δ as shown below

Present State Next State for Input ‘0’ Next State for Input ‘1’

a a, b b
b c a, c
c b, c c
Its graphical representation would be as follows
DIFFERENCE BETWEEN DFA & NFA:
S.NO DFA NFA
1. In DFA, the next possible state is In NFA, each pair of state and
distinctly set. input symbol can have many
possible next states.
2. DFA cannot use Empty String NFA can use Empty String
transition. transition.
3. DFA requires more space. NFA requires less space then DFA.
4. Time needed for executing an Time needed for executing an
input string is less. input string is more.
5. DFA can be understood as one NFA can be understood as
machine. multiple little machines
computing at the same time.
6. It is not possible to move next It can move to next state without
state without reading any symbol. reading any symbol.
FINITE AUTOMATA WITH Ɛ-MOVES:

The closure (p) is a set of all states which are reachable

from state p on Ɛ-transitions such that
i) Ɛ closure(p) = p where p € Q.
ii) If there exists Ɛ closure(p) = {q} and δ(q, Ɛ)=r
then Ɛ closure(p) = {q , r} .
BEYOND SYLLABUS
( NFA TO DFA)
THANK YOU