Cs6503 theory of computation book notes

Cs6503 theory of computation book notes computer science and engineering anna university 5 fifth semester

1. THEORY
OF
COMPUTATION




G. Appasami, M.Sc., M.C.A., M.Phil., M.Tech., (Ph.D.)
Assistant Professor
Department of Computer Science and Engineering
Dr. Paul’s Engineering Collage
Pauls Nagar, Villupuram
Tamilnadu, India



SARUMATHI PUBLICATIONS
Villupuram, Tamilnadu, India

2. First Edition: July 2016




Published By
SARUMATHI PUBLICATIONS
© All rights reserved. No part of this publication can be reproduced or stored in any form or
by means of photocopy, recording or otherwise without the prior written permission of the
author.




Price Rs. 101/-



Copies can be had from
SARUMATHI PUBLICATIONS
Villupuram, Tamilnadu, India.
[email protected]



Printed at
Meenam Offset
Pondicherry – 605001, India

3. Acknowledgement




I am very much grateful to the management of paul’s educational trust, Respected
principal Dr. Y. R. M. Rao, M.E., Ph.D., cherished Dean Dr. E. Mariappane, M.E.,
Ph.D., and helpful Head of the department Mr. M. G. Lavakumar M.E., (Ph.D.).


I thank my colleagues and friends for their cooperation and their support in my
career venture.


I thank my parents and family members for their valuable support in completion of
the book successfully.


I express my special thanks to SARUMATHI PUBLICATIONS for their continued
cooperation in shaping the work.


Suggestions and comments to improve the text are very much solicitated.





Mr. G. Appasami

5. CS6503 THEORY OF COMPUTATION L T P C 3 0 0 3

OBJECTIVES:
The student should be made to:
 Understand various Computing models like Finite State Machine, Pushdown Automata,
and Turing Machine.
 Be aware of Decidability and Un-decidability of various problems.
 Learn types of grammars.

UNIT I FINITE AUTOMATA 9
Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic
Definitions – Finite Automaton – DFA & NDFA – Finite Automaton with €- moves – Regular
Languages- Regular Expression – Equivalence of NFA and DFA – Equivalence of NDFA‟s
with and without €-moves – Equivalence of finite Automaton and regular expressions –
Minimization of DFA- - Pumping Lemma for Regular sets – Problems based on Pumping
Lemma.

UNIT II GRAMMARS 9
Grammar Introduction– Types of Grammar - Context Free Grammars and Languages–
Derivations and Languages – Ambiguity- Relationship between derivation and derivation
trees – Simplification of CFG – Elimination of Useless symbols - Unit productions - Null
productions – Greiback Normal form – Chomsky normal form – Problems related to CNF
and GNF.

UNIT III PUSHDOWN AUTOMATA 9
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic
pushdown automata – Equivalence of Pushdown automata and CFL - pumping lemma for
CFL – problems based on pumping Lemma.

UNIT IV TURING MACHINES 9
Definitions of Turing machines – Models – Computable languages and functions –
Techniques for Turing machine construction – Multi head and Multi tape Turing Machines -
The Halting problem – Partial Solvability – Problems about Turing machine- Chomskian
hierarchy of languages.

UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS 9
Unsolvable Problems and Computable Functions – Primitive recursive functions –
Recursive and recursively enumerable languages – Universal Turing machine.
MEASURING AND CLASSIFYING COMPLEXITY: Tractable and Intractable problems-
Tractable and possibly intractable problems - P and NP completeness - Polynomial time
reductions.

TOTAL: 45 PERIODS

TEXT BOOKS:
1. Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory, Languages and
Computations”, Second Edition, Pearson Education, 2008. (UNIT 1,2,3)
2. John C Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, Tata
McGraw Hill Publishing Company, New Delhi, 2007. (UNIT 4,5)

REFERENCES:
1. Mishra K L P and Chandrasekaran N, “Theory of Computer Science - Automata, Languages and
Computation”, Third Edition, Prentice Hall of India, 2004.
2. Harry R Lewis and Christos H Papadimitriou, “Elements of the Theory of Computation”, Second
Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003.
3. Peter Linz, “An Introduction to Formal Language and Automata”, Third Edition, Narosa
Publishers, New Delhi, 2002.
4. Kamala Krithivasan and Rama. R, “Introduction to Formal Languages, Automata Theory and
Computation”, Pearson Education 2009

6. TABLE OF CONTENTS


S. No. Contents Page no.
UNIT I FINITE AUTOMATA
1 Introduction - Basic Mathematical Notation and techniques
2 Finite State systems - Basic Definitions Finite Automaton
3 DFA & NDFA
4 Finite Automaton with ε- moves
5 Regular Languages - Regular Expression
6
Equivalence of NFA and DFA
Equivalence of NDFA’s with and without ε - moves

7 Equivalence of finite Automaton and regular expressions
8 Minimization of DFA
9 Pumping Lemma for Regular sets
10 Problems based on Pumping Lemma
UNIT II GRAMMARS
1 Grammar Introduction - Types of Grammar
2 Context Free Grammars and Languages
3 Derivations and Languages Ambiguity
4 Relationship between derivation and derivation trees
5 Simplification of CFG
6
Elimination of Useless symbols
Unit productions - Null productions

7 Greiback Normal form

7. 8 Chomsky normal form
9 Problems related to CNF and GNF
UNIT III PUSHDOWN AUTOMATA
1 Pushdown Automata
2 Definitions
3 Moves
4 Instantaneous descriptions
5 Deterministic pushdown automata
6 Equivalence of PDA and CFL
7 Pumping lemma for CFL
8 Problems based on pumping Lemma
UNIT V TURING MACHINES
1 Definitions of Turing machines
2 Models
3 Computable languages and functions
4 Techniques for Turing machine Construction
5 Multi head and Multi tape Turing Machines
6 The Halting problem
7 Partial Solvability
8 Problems about Turing machine
9 Chomskian hierarchy of languages

UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE
FUNCTIONS

1 Unsolvable Problems and Computable Functions

8. 2 Primitive recursive functions
3 Recursive and recursively enumerable languages
4 Universal Turing machine.
5 Measuring and classifying complexity
6 Tractable and Intractable problems
7 Tractable and possibly intractable problems
8 P and NP completeness
9 Polynomial time reductions

2 Marks Questions and Answers 74
Question Bank 100
Model Question paper 105
References 107

9. Theory of Computation 1

THEORY OF COMPUTATION

UNIT I - AUTOMATA

The theory of computation is the branch that deals with whether and how efficiently
problems can be solved on a model of computation, using an algorithm. The field is divided
into three major branches: automata theory, computability theory and computational
complexity theory.

1.1 Introduction to formal proof

Formal Proofs are the proofs in which we try to prove the statement ‘B’ is true
because statement ‘A’ is true. In other words, the Statement “If A then B” means that B is
deduced from A. In this statement A is called hypothesis and B is called conclusion
statement.
The formal proofs can be done by deductive proof and inductive proof.

1.1.1 Deductive Proof
It consists of a sequence of statements given with logical reasoning in order to prove
the first (or initial) statement. The first statement is called hypothesis.

1.1.2 Inductive Proof
It is a recursive kind of proof which consists of sequence of parameterized statements
that cure statement itself with lower values of its parameters.

1.1.3 Additional forms of Proofs
I. Proofs about sets
II. Proofs by contradiction
III. Proofs by counter example

Proofs about sets
Set is a collection of elements or items. Let us consider two sets A and B. Define the
expression R as union of A and B (i.e. AUB) and S as union of B and A (i.e. BUA), where U
is the Union operation U on two sets A and B such that if x ϵ AUB iff x is in A or x is in B.

Prove that R=S(i.e, x is in R if and only if it is in S)

Proof:
To prove R=S, we have to prove AUB=BUA
(i)x is in AUB then it is in BUA
Sl. No. Statement Justification
1 x is in AUB Given
2 x is in Aor x is in B By definition of union & (1)
3 x is in B or x is in A By definition of union & (2)
4 x is in BUA By definition of union & (3)

(i) x is in BUA then it is in AUB
Sl. No. Statement Justification
1 x is in BUA Given

10. Theory of Computation 2

2 x is in B or x is in A By definition of union & (1)
3 x is in Aor x is in B By definition of union & (2)
4 x is in AUB By definition of union & (3)

So AUB=BUA, Thus R=S is true, Hence proved.

Proofs by contradiction
In proof by contradiction, to prove the statement of the form “if A true then B true”,
We start with statement A is not true by assumption and try to get the conclusion statement B.
When it impossible to reach B then we contradict our self and accept that A is true.
Example: Prove PUQ = QUP
Proof:
Initially assume, PUQ = QUP is not true
i.e. PUQ ≠ QUP
Now consider, x is in PUQ
x is in P or x is in Q (By Definition of Union)
x is in Q or x is in P (By Definition of Union)
x is in QUP (By Definition of Union)
This contradicts our assumption PUQ ≠ QUP
Hence the assumption which we made initially is false
Therefore PUQ = QUP is proved.

Proofs by counter example
In order to prove certain statements, we need to check all the possible conditions in
which that statement remains true. There are some situations in which the statement cannot
be true.

Example 1: There is no pair of integers a and b such that amod b = b mod a
Proof: There are two possibilities. They are either a>b or a<b.
If a=2 and b=3 then 2 mod 3 ≠ 3 mod 2
If a=3 and b=2 then 3 mod 2 ≠ 2 mod 3
If a=b=2 then 2 mod 2 = 2 mod 2, so the given statement is true only if a=b, so we have to
change the statement slightly, Thus, amod b = b mod a true only when a=b,
We proved by counter example, this type of proof is called proof by counter example. Such
proof are true only at specific conditions.

Example 2: All primes are odd numbers.
2, 3, 5 ,7 1, 13, 17, 23, . . are prime numbers and all are odd numbers except 2.
The integer 2 is prime but not odd, so the statement is not a theorem.

Example 1
Prove that every integer n ≥ 0, the number 4
2n + 1
+ 3
n + 2
is multiple of 13 by induction.
Proof: Let n= 0, P(0) = 4
2(0) + 1
+ 3
(0) + 2
= 4
1
+ 3
2
= 4 + 9 = 13 = 13.t where t=1
Let n = 1, P(1) = 4
2(1) + 1
+ 3
(1) + 2
= 4
3
+ 3
3
= 64 + 27 = 91 = 13.t where t= 7
Let n = k, P(k) = 4
2(k) + 1
+ 3
(k) + 2
= 4
2k + 1
+ 3
k + 2
= 13.t, true for some integer t

11. Theory of Computation 3

Let n = k + 1, P(k + 1) = 4
2(k + 1) + 1
+ 3
(k + 1) + 2

= 4
2(k + 1) + 1
+ 3
(k + 1) + 2

= 4
2k + 2 + 1
+ 3
k + 1 + 2

= 4
2k + 1 + 2
+ 3
k + 2 + 1
= 4
2k + 1.
4
2
+ 3
k + 2.
3
1
= 4
2
.4
2k + 1
+ 3.3
k + 2
= 4
2
.4
2k + 1
+ 4
2
3
k+2
- 4
2
3
k+2
+ 3.3
k + 2
{ Add & Sub 4
2
3
k+2
}

= 4
2
(4
2k + 1
+ 3
k+2
) + 3
k+2
(-4
2
+ 3)

= 4
2
(13.t)- 3
k+2
(-4
2
+ 3)

{ 4
2k + 1
+ 3
k + 2
= 13.t}

= 16 (13.t)- 3
k+2
(-13)

= 13[16. t + 3
k+2
]
= Multiple of 13
฀ P(k + 1) is multiple of 13, Hence proved.


Example 2
Prove 1 + 2 + 3 + … + n = n (n+1)/2 using induction method.
Proof:
Let n = 1, then LHS = 1 and RHS = 1 (1 + 1) / 2 = 1
LHS = RHS
Let n = 2, then LHS = 1 + 2 = 3 and RHS = 2(2 + 1) / 2 = 3
LHS = RHS
Let n = k, 1 + 2 + 3 + … + k = k (k+1)/2
Consider n = k +1, then LHS = 1 + 2 + 3 + … + k + (k+1) = (k+1) (k+2) / 2
RHS = k (k+1)/2 + (k + 1)
= k
2
+ k + 2 (k + 1)
2 2
= (k
2
+ 3k + 2) / 2
= (k+1) (k+2) / 2
LHS = RHS
Hence Proved.
Example 3
Show that 2
n
> n
3
for n ≥ 10 by mathematical induction.
Proof:

Let n= 10, 2
10
> 10
3
, 1024 > 1000, ฀ The condition is true.

12. Theory of Computation 4

Let n= 11, 2
11
> 11
3
, 2048 > 1331, ฀ The condition is true.
Let n = 12, 2
12
> 12
3
, 4096 > 1728, ฀ The condition is true.
Let n = k, 2
k
> k
3
, Assume the condition is true for k.
Let n = k +1, 2
k+1
= 2
k
.2
1
= 2
k
.2
1
> k
3
.2
1
฀ 2
k+1
> k
3
.2
1
Let k =12 in above inequality, LHS = 2
12+1

= 2
13
= 8192
RHS = 12
3
.2 = 3456
฀ LHS  RHS, Hence Proved.

Example 4
Show that n! >= 2
n - 1
by mathematical induction.
Proof:
Let n = 1, LHS = 1! = 1 RHS = 2
1 - 1
= 2
0
= 1
LHS >= RHS
Let n = 2, LHS = 2! = 2.1 = 2 RHS = 2
2 - 1
= 2
1
= 2
LHS >= RHS
Let n = 3, LHS = 3! = 3. 2.1 = 6 RHS = 2
3 - 1
= 2
4
= 4
LHS >= RHS
Let n = k, k! >= 2
k – 1

Let n = k + 1 (k + 1)!= (k + 1) k!
>=(k + 1) 2
k – 1
(k + 1)!>=(k + 1) 2
k – 1

Let k=2, LHS = (2+1)! = 3! =6
RHS = (2+1)2
2- 1
=3.2 = 6
฀ LHS  RHS, Hence Proved.

13. Theory of Computation 5


Example 4
Prove by mathematical induction Ʃn
2
=
?:?+5;:6?+5;
:
for all n ≥ 1.
Proof:
1
2
+ 2
2
+ ... + n
2
=
?:?+5;:6?+5;
:

Let n = 1, LHS = 1
2
= 1, RHS =
5:5>5;:6?5>5;
:
=
5 &#3627408485; 6 &#3627408485; 7
:
= 1, ฀ LHS = RHS
Let n = 2, LHS = 1
2
+ 2
2
= 1 + 4 = 5, RHS =
6:6>5;:6?6>5;
:
=
6 &#3627408485; 7 &#3627408485; 9
:
= 5, ฀LHS = RHS
Let n = k, 1
2
+ 2
2
+ ... + k
2
=
?:?+5;:6?+5;
:
, assumed to be true
Let n = k+1, LHS = 1
2
+ 2
2
+ ... + k
2
+ (k + 1)
2
=
?:?+5;:6?+5;
:
+ (k + 1)
2
=
?:?+5;:6?+5;
:
+ (k + 1) (k +1)

=
?:?+5;:6?+5;
:
+
::?+5;:?+5;
:

=
?:?+5;:6?+5;+::?+5;:?+5;
:

=
:?+5;[?:6?+5;+::?+5;]
:

=
:?+5;( 6?
2
+ ?+:?+:)
:

=
:?+5;( 6?
2
+ ;?+:)
:

=
:?+5;: ?+6;:6?+7;
:

RHS =
:?+5;:?+5+5;:6[?+5]+5;
:

=
:?+5;:?+6;:6?+6+5;
:

=
:?+5;: ?+6;:6?+7;
:

฀ LHS = RHS, Hence Proved

14. Theory of Computation 6

Alphabets, Strings and language
Alphabet:
An alphabet is a finite non empty set of symbols. The symbol Σ is used to denote the
alphabet.
1) Σ = {0, 1}
2) Σ = {a, b, c, …, z}
3) Σ = Set of ASII character

String:
A string is a finite sequence of symbols chosen from some alphabet.
1) Σ ={0,1}  11001 [ Empty string is denoted by 0]
2) Σ = {a, b, c}  aabbcbbbaa

The total number of symbols in the string is called length of the string
Example:
1) |0001|=4
2) |100|=3
Empty string (0):
Empty string is the string with zero occurrence of symbol .This empty string is denote
by 0
Power of an alphabet
If Σ is an alphabet, then the set of all string of certain length forms an alphabet .
Σ
k
to be the set of string of length k for each symbol in Σ.
Example :
∑

= {0, 1}
∑
4
={ 0 }
∑
5
= {0, 1}
∑
6
= {00, 01, 10, 11}
∑
7
= {000, 001, 010, 011, 100, 101, 110, 111}

15. Theory of Computation 7

∑
+
= ∑ &#3627408456;
5
∑&#3627408456;
6
∑
7
…
∑
+
= ∑
?
⋃
∞
?=5
∑
∗
= ∑&#3627408456;
4
∑&#3627408456;
5
∑&#3627408456; …
6

∑
∗
= ∑
?
⋃
∞
?=4
Set of all strings over an alphabet is denoted by ∑
∗

Set of all strings over an alphabet except null string is denoted by ∑
+


Concatination of strings
Let X and Y be the two strings over Σ = {a, b, c}. Then XY denotes the concatenation
of X and Y.
X = aabb
Y = cccc
XY = aabbcccc
YX = ccccaabb

Language [Language is a collection of all strings]
A set of strings of all which are chosen from ∑
∗
is called a language, where ∑

is a
particular alphabet set.
Finite state system (or) finite automata :
A finite automata has a several parts. It has set of states and rules for moving from
one state to another state depending on the input symbols.
It has the input alphabet, start state, and a set of accept state.
Definition of finite automata:
A finite automata is a collection of 5-tuples A = (Q , ∑, / , q
0
, F)
Where A  Name of the finite automata
Q  Finite set of states [non-empty]
∑  The set of input symbols [input set]
/  The transition function [Move from one state to another ] /:Qx ΣQ

16. Theory of Computation 8

q
0


q
1
q
2
q
3

1 1
Start
1
q
0


q
1
q
3

0 1
Start
0 1
0
q
0
 Initial or start state q
0∈Q


F  Set of all final states

Types of finite automata (FA)
 Deterministic finite automata (DFA)
 Non deterministic finite automat (NFA)
Transition diagram
Transition diagram for a DFA A = (Q, ∑, /, q0, F) is a graph define as follows
o For each state q in Q there is a node.
o For each state q in Q and each input symbol a in ∑

then the transition
diagram has an arc from node q to node p.
Transition table
A transition table is a conventional table represent of a function like / in finite
automata. That takes two argument and return a value. The rows of the table correspond to
the state and column corresponds to the input symbols.
Deterministic finite automata:
Finite automata are called Deterministic automata if there is only one path for its
specified input from current state to next state.
Example 1 Design Finite Automata (FA) which accepts only input 111 over the input set Σ =
{1}
Solution:

Example 2 Design FA which accepts only those strings which start with 0 and end with 1
over the input set Σ = {0, 1}
Solution:

a b c a a b c a Input tape
Finite
control
Tape head /
reader

17. Theory of Computation 9

Input
0
q
0

q
1


q
1

q
1


q
2

q
2


1
q
2

q
2


q
1



States
q
2

1 1
Start
1

1
Input
0
q
0

q
1


q
1

q
1


q
2
q
3


1
q
2

q
2


q
1



States
q
3
q
2


q
3


q
0


q
2

0
0
Start
1
1
q
1
q
3


0
0


1
1 0
q
0


q
1

q
2

0
1
Start
0
0

1 1
Example 3 Design FA & State Table which accepts odd number of 1’s and any number of
0’s.




State Transition Diagram State Transition Table
FA A = (Q, ∑, /, q0, F)
= ({q 0, q1, q2}, {0, 1}, {/(q0, 0)= q1, /(q0, 1)= q2, /(q1, 0)= q1, /(q1, 1)= q2 , /(q2, 0)=
q2, /(q2, 1)= q1 }, q0, {q2})
Check: 0110 & 1110
q
0
0110  0q
1
110  01q
2
10  011q
1
0  0110q
1
 Reached non final state  not accepted
q
0
1110  1q
2
110  11q
1
10  111q
2
0  1110q
2
Reached final state  string accepted

Example 4 Design FA which accepts the unary number which is divisible by 3 over Σ = {1}.


Check: 111 & 1111
q
0
111  1q
1
11  11q
2
1  111q
3
 Reached final state  String accepted
q
0
1111  1q
1
111  11q
2
11  111q
3
1  1111q
1
 Reached non final state  not accepted

Example5 Design FA & State Table which accepts the binary number which is divisible by 3.





State Transition Diagram State Transition Table

18. Theory of Computation 10

Input
a
s
0

s
1


s
1

s
2


s
3


s
1


b
s
0


s
3



States
s
2

s
3




b
s
0


s
2
s
3

a a
s
1


a
b
a
Input
0
q
0

q
1


q
1

q
1


q
2

q
2


1
q
2

q
2


q
1



States
q
0


q
2

q
1

0
Start
0
1
0 1
1
q
0


q
0


q
0


b
a
b

b

rt Start
Start
Check: 9 & 8 (i.e. 1001 &1000 )
q
0
1001  1q
2
001  10q
3
01  100q
2
1 1001q
1
 Reached final state  String accepted
q
0
1000  1q
2
000  10q
3
00 100q
2
0 1000q
3
 non final state  not accepted

Example 6 Design FA to accept L, where L= {Strings in which ‘a’ always appears tripled}
over the input set Σ = {a, b}.





Example 7 Design FA which checks the given binary number is even.




State Transition Diagram
State Transition Table
Check: 6 & 7 (i.e. 0110 & 0111)
q
0
0110  0q
1
110  01q
2
10  011q
2
0  0110q
1
 Reached final state  string accepted
q
0
0111  0q
1
111  01q
2
11  011q
2
1  0111q
2
 Reached non final state  not accepted

Non deterministic automata:

19. Theory of Computation 11

q
1
q
3
q
4

0 01
Start q
2

1
q
6

0
0
0
q
5

1
q
2

1
Start
1
0

0
0


0
q
1

0
0
1
q
3

Finite automata is also called as non deterministic automata when many paths are
specified in code from the current state to next state
N FA can be defined as the collection of five tuple
A ={Q , ∑ , / , qo , F}
Example : 1 construct NFA where L={0101* + 0100 n ≥ 0} over the string ∑={0,1}











Example 2 : construct the transmission diagram for NFA where
M=({ q1 q2 q3 } , {0,1} , / , q1 , { q3 } )
Where / is given by
/’(q1 , 0) = { q2 , q3} /’(q1 , 1)= { q1 }
/’(q2 , 0) = { q1 , q2} /’(q2 , 1)={ ɸ }
/’(q3 , 0) = { q2 } /’(q3 , 1)= { q1 , q2 }
sol :




State\ip 0 1
q
1
q
2
ɸ
q
2
ɸ q
3

q
3
{q
4
, q
5
} ɸ
q
4
ɸ q
4

q
5
q
6
ɸ
q
6
ɸ ɸ

20. Theory of Computation 12






NFA with Epsilon transition:
The 0 transition in NFA is given in order to move from one state to another without
having any symbol from input.

state 0 1
q1 {q2 , q3} q1
q2 {q1 , q2} ɸ
q3 q2 {q1 , q2}

21. Theory of Computation 13

q
0

q
q
2
Start q
1

q
0
b c
0
a
q
0


q
2


Start q
1


0
b
a
Definition:
The language L is accepted by NFA with 0 denoted by M ={Q , ∑ , / , qo , F} can be
defined as follow .
Q x ( ∑ u { 0 } )  2
Q

L(M) ={ w/w € ∑
∗
}
Epsilon closure (p) :
It is set of all state which are reachable from state p or epsilon transition such that
1) 0 closure (p) ={p}, Where p € Q
2) If there exist 0 -closure (p) ={q} and / ( q , 0 ) = r , then 0 closure (p) ={q, r}.
Example 1: Find the 0 closure for the following NFA with 0




0 closure(q0 )={ q0 , q1 , q2}
0 closure(q1)={ q1 , q2}
0 closure(q2)={q2 }
Conversion from NFA with 0 to NFA without 0 :
1) Find all the 0 transition for each state from Q that will be called as 0 closure { qi }
Where { qi } is the element of Q
2) /’ transition can be obtained from / transition. i.e., an 0 closure of /.
3) Step 2 is repeated for each input symbol and for each state of given NFA.
4) Using the resultant state the transition table for equivalent NFA without 0 can be
built .
/’(q, a) = 0 closure(/ (/
^
(q, 0), a))


Example 1: Convert the given NFA with 0 transition to NFA without 0 transition.

22. Theory of Computation 14

Step 1: 0 closure
0 closure (q0 )={ q0 }
0 closure (q1 )={ q1 , q2 }
0 closure (q2 )={ q2 }
Step 2:
/’(q0 , a) = q1 /’(q0 , b) = ɸ /’ (q0, 0) = ɸ
/’(q1 , a) = ɸ /’(q1 , b) = ɸ /’ (q1, 0) = q2
/’(q2 , a) = ɸ /’(q2 , b) = q2 /’ (q2, 0) = ɸ
Step 3:
/’(q0, a) = 0 closure(/ (/
^
(q0 , 0), a))
= 0 closure(/ (0 closure (q0 ), a))
= 0 closure(/ (q0, a))
= 0 closure(q1)
= { q1 , q2 }
/’(q0 , b) = 0 closure(/(/
^
(q0 , 0), b))
= 0 closure(/ (0 closure (q0 ), b))
= 0 closure(/ (q0 , b))
= 0 closure ɸ
= { ɸ }
/’(q1, a) = 0 closure(/ (/
^
(q1 , 0), a))
= 0 closure(/ (0 closure (q1 )a))
= 0 closure(/ ({q1 , q2 }, a))
= 0 closure(/(q1 , a) U /(q2 , a))
= 0 closure (ɸ U ɸ)
= 0 closure (ɸ)
= { ɸ }

23. Theory of Computation 15

q
2


Start
b
b
a
q
2
q
2

a

/’(q1, b) = 0 closure(/(/
^
(q1 , 0),b))
= 0 closure(/(0 closure (q1 )b))
= 0 closure(/ ({q1 , q2} , b))
= 0 closure(/(q1 , b) U /(q2 , b))
= 0 closure (ɸ U q2)
= 0 closure ( q2 )
= { q2 }
/’(q2, a) = 0 closure(/ (/
^
(q2 , 0), a))
= 0 closure(/ (0 closure (q2 ), a))
= 0 closure(/ ( q2, a))
= 0 closure ɸ
= { ɸ }

/’(q2, b) = 0 closure(/(/
^
(q2 , 0), b))
= 0 closure(/(0 closure (q2 ), b))
= 0 closure(/( q2 , b))
= 0 closure (q2 )
= { q2 }
Transition table :


Step 4:
Transition diagram : NFA without 0




state a b
q0 {q1 ,q2} ɸ
q1 ɸ q2
q2 ɸ q2

24. Theory of Computation 16

q
0


q
2


Start q
1


0
b c
0
a
Example 2 : Construct NFA with 0 which access a language consisting of a string of any
number of ‘a’ followed by any number of ‘b’ and followed by any number ‘ c ‘. Convert
the NFA with 0 to NFA without 0.
sol :



Step 1: 0 closure
0 closure (q0 )={ q0 , q1 , q2 }
0 closure (q1 )={ q1 , q2 }
0 closure (q2 )={ q2 }
step 2:
/(q0 , a) = q0 /(q0 , b) = ɸ / (q0, c) = ɸ / (q0, 0) = q1
/(q1 , a) = ɸ /(q1 , b) = q1 / (q1, c) = ɸ / (q1, 0) = q2
/(q2 , a) = ɸ /(q2 , b) = ɸ / (q2, c) = q2 / (q2, 0) = ɸ
Step 3:
/’(q0, a) = 0 closure(/ (/
^
(q0 , 0), a))
= 0 closure(/ (0 closure (q0 ), a))
= 0 closure(/(q0, a) &#3627408456; /(q1, a) &#3627408456; /(q2, a))
= 0 closure ( q0 Uɸ U ɸ)
= 0 closure ( q0 )
= { q0 , q1 , q2 }
/’(q0, b) = 0 closure(/(/
^
(q0 , 0), b))
= 0 closure(/(0 closure (q0 )b))
= 0 closure(/(q0, b) &#3627408456; /(q1, b) &#3627408456; /(q2, b))
= 0 closure (ɸ &#3627408456;q1 &#3627408456;ɸ)
= { q1 , q2 }
/’(q0, c) = 0 closure(/(/
^
(q0, 0), c))

25. Theory of Computation 17

= 0 closure(/(0 closure (q0 ), c))
= 0 closure(/(q0, c) &#3627408456; /(q1, c) &#3627408456; /(q2, c))
= 0 closure (ɸ Uɸ Uq2)
= { q2 }
/’(q1, a) = 0 closure(/ (/
^
(q1, 0), a))
= 0 closure(/(0 closure (q1 ), a))
= 0 closure(/(q1, a) &#3627408456; /(q2, a))
= 0 closure (ɸ &#3627408456; ɸ )
= 0 closure (ɸ)
= { ɸ}
/’(q1, b) = 0 closure(/ (/
^
(q1 , 0),b))
= 0 closure(/(0 closure (q1 )b))
= 0 closure(/(q1, b) &#3627408456; /(q2, b))
= 0 closure (q1)
= {q1 , q2}
/’(q1, c) = 0 closure(/ (/
^
(q1 , 0), c))
= 0 closure(/(0 closure (q1 ), c))
= 0 closure(/(q1, c) &#3627408456; /(q2, c))
= 0 closure (ɸ&#3627408456;q2)
= {q2}
/’(q2, a) = 0 closure(/ (/
^
(q2 , 0), a))
= 0 closure(/ (0 closure (q2 ), a))
= 0 closure(/(q2, a))
= 0 closure (ɸ)
= { ɸ}
/’(q2, b) = 0 closure(/ (/
^
(q2 , 0), b))
= 0 closure(/(0 closure (q2 ), b))

26. Theory of Computation 18

q
0


q
2


Start q
1


a, b
a
a, b
b c
b
= 0 closure(/(q2, b))
= 0 closure (ɸ)
= { ɸ}
/’(q2,c) = 0 closure(/ (/
^
(q2 , 0), c))
= 0 closure(/ (0 closure (q2 ), c))
= 0 closure(/(q2, c))
= 0 closure (q2)
= {q2}
Step 4:
Transition table
state a b c
q0 {q0, q1, q2} {q1 ,q2} q2
q1 ɸ {q1 ,q2} q2
q2 ɸ ɸ q2


Transition diagram:






Conversion N.F.A to D.F.A
L et M={Q , ∑ , / , qo , F} is the NFA which accepts the language L(M) then there
should be equivalent DFA denoted by M’={ Q’ , ∑’ , /’ , qo’ , F’} such that L(M)=L(M’).

27. Theory of Computation 19

Conversion Steps:
STEP 1: The start state of NFA M will be the start state of DFA M’. Hence add qo of NFA to
Q’ then, find the transition for this start state.
STEP 2: For each state {q1, q2, q3……qi} in Q’. The transition for each input symbol ∑ can
be obtained as follows,
(i) /’( [q1,q2,q3……qi], a) = /(q1,a ) U (q2, a)…… U /(qi, a)
= [q 1, q2, q3, ... , qk]
(ii) Add the [q1, q2, q3, ... , qk] in DFA if it is not already in Q.
(iii) Then, find the transition for every input symbol from ∑ for states [q1, q2,
q3, ... , qk], if we get some state [q1,q2…..qn] which is not Q’ of DFA then add
this to Q’.
(iv) If there is no new state generating then stop the process after finding all
the transition.
(v) For the state [q1, q2, q3, ... , qk] € Q’ of DFA, if any 1 state qi is a final
state of NFA then [q1,q2…..qn] becomes a final state. Thus the set of all final
states € F’ of DFA.

Example 1: Construct the equivalent DFA for the given NFA.
M = ({q0, q1}, {0,1}, /, qo, {q1}) where / is given by
/ (q0,0) = {q0, q1}
/ (q0,1) = { q1}
/ (q1,0) = φ
/ (q1,0) = {q0, q1}
Sol:
Transition Table (NFA)

St/Ip 0 1
q0 {q0, q1}

{q1}
q1 φ {q0, q1}

28. Theory of Computation 20

Transition Diagram:

/’( {q0, q1}, 0) = /(q0, 0) U /(q1, 0)
= { q 0, q1} U φ
= { q0, q1}
/’( {q0, q1}, 1) = /(q0,1) U /(q1, 1)
= { q 1} U { q0, q1}
= { q0, q1}
Transition Table:
St/Ip 0 1
qo {q0, q1} {q1}
q1 φ {q0, q1}
{q0, q1} {q0, q1} {q0, q1}

Transition Diagram: (DFA)

29. Theory of Computation 21


ssq

q
Example 2. Construct an DFA equivalent to the given NFA.
St/Ip 0 1
→p {p, q} p
q r r
r s φ
s s s

Sol.
Transition Diagram:

Transition Table:
St/Ip 0 1
→P {p, q} p
q r r
r s φ
s s s

/’( {p, q}, 0) = /( p,0) U /( q,0)
= {p, q} U {r}
= {p, q, r}
/’({p, q}, 1) = /( p,1) U /( q,1)
= {p} U {r}
= {p, r}

30. Theory of Computation 22


q

q
New State table:
St/Ip 0 1
→P {p, q} p
q r r
r s φ
s s s
{p, q} {p, q, r} {p, r}

/’({p, q, r}, 0) = /( p,0) U /( q,0) U /( r,0)
= {p, q} U {r} U {s}
= {p, q, r, s}
/’({p, q, r}, 1) = /( p,1) U /( q,1) U /( r,1)
= {p} U {r} U { φ }
= {p, r}
/’({p, r}, 0) = /( p,0) U /( r,0)
= {p, q} U {s}
= {p, q, s}
/’({p, r}, 1) = /( p,1) U /( r,1)
= {p} U { φ }
= {p}
New transition table:
St/Ip 0 1
→P {p, q} p
q r r
r s φ
s s s

31. Theory of Computation 23



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

/’({p, q, r, s}, 0) = /( p,0) U /( q,0) U /( r,0) U /( s,0)
= {p,q} U {r} U {s} U {s}
= {p, q, r, s}
/’({p, q, r, s}, 1) = /( p,1) U /( q,1) U /( r,1) U /( s,1)
= {p} U {r} U { φ } U {s}
= {p, r, s}
/’( [p,q,s],0) = /( p,0) U /( q,0) U /( s,0)
= {p,q} U {r} U {s}
= {p, q, r, s}
/’( [p,q,s],1) = /( p,1) U /( q,1) U /( s,1)
= {p,q} U {r} U {s}
= {p, q, r, s}
New transition table:
St/Ip 0 1
→P {p, q} p
q r r
r s φ
s s s
{p, q} {p, q, r} {p, r}
{p, q, r} {p, q, r, s} {p, r}
{p, r} {p, q, s} p
{p,q,r,s} {p, q, r, s} {p, r, s}

32. Theory of Computation 24




q
2


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

/’({p, r, s}, 0) = /( p,0) U /( r,0) U /( s,0)
= {p,q} U {s} U {s}
= {p, q, s},
/’({p, r, s}, 1) = /( p,1) U /( r,1) U /( s,1)
= {p} U {s} U {s}
= {p, s}
New transition table:
St/Ip 0 1
→[P] [p,q] [ p]
[q] [r] [ r]
[r] [s] φ
s [s] [s]
[p,q] [p,q,r] [p,r]
[p,q,r] [p,q,r,s] [p,r]
[p,r] [p,q,s] [p]
p,q,r,s [p,q,r,s] [p,r,s]
p,q,s [p,q,r,s] [p,r,s]
p,r,s [p,q,s] [p,s]

/’( [p,s],0) = /( p,0) U /( s,0)
= {p,q} U {s}
= [p,q,s]
/’( [p,s],1) = /( p,1) U /( s,1)
= {p} U {s}
= [p,s]

33. Theory of Computation 25

New transition table:

Transition Diagram: (DFA)






METHOD FOR CONVERSION NFA WITH 0 TO DFA
Step 1 : Consider M={Q, ∑, /, q0, F} is a NFA with 0 , we have to convert this NFA with 0 to
equivalent DFA,
MD =( QD,∑ D, /D, qD, FD). Obtain 0 closure (q0 ) = { p1p2……pn } becomes its start
state of DFA.
Step2 : Obtain / transition on { p1p2……pn } for each input.
/D ({ p1p2……pn }, a) = 0 closure( /(P1 ,a) U /(P2 (a) U ……U(Pn ,a))
= ⋃0 closure /:Pi , a;
?
?=5 where a ϵ ∑
Step3 : State obtained [ P1P2……Pn ] ϵ QD , states containing final state Pi is a final state
DFA.
St/Ip 0 1
→[P] [p,q] [ p]
[q] [r] [ r]
[r] [s] -
[s] [s] [s]
[p,q] [p,q,r] [p,r]
[p,q,r] [p,q,r,s] [p,r]
[p,r] [p,q,s] [p]
[p,q,r,s] [p,q,r,s] [p,r,s]
[p,q,s] [p,q,r,s] [p,r,s]
[p,r,s] [p,q,s] [p,s]
[p,s] [p,q,s] [p,s]

34. Theory of Computation 26

EXAMPLE 1: Convert the following NFA with 0 to equivalent DFA.

b a

0 0

a
b
0 closure(q0 )={ q0 q1 q2}
0 closure(q1)={ q1 q2}
0 closure(q2)={q2 }

/(q0 , a) = ɸ /(q0 , b) = q0 /(q1, 0) = q1
/(q1 , a) = q1 /(q1 , b) = ɸ /(q2, 0) = q2
/(q2 , a) = q1 /(q2 , b) = q0 /(q2, 0) = ɸ

/’(q0 , a) = 0 closure(/(/
^
(q0,0),a))
/’(q0 , a) = 0 closure(/(0 closure q0 ),a))
= 0 closure(/({q0 q1 q2 } ,a) )
= 0 closure(/(q0 ,a)U /(q1 ,a)U /(q2 ,a) )
= 0 closure(ɸ U q1 U q1 )
= 0 closure q1
= { q 1 q2}
/’(q0 , b) = 0 closure(/(/
^
(q0,0),b))
/’(q0 , b) = 0 closure(/(0 closure q0 ),b))
= 0 closure(/({q0 q1 q2 } ,b) )
= 0 closure(/(q0 ,b)U /(q1 ,b)U /(q2 ,b) )
q0
q1
q2

35. Theory of Computation 27

= 0 closure(q0 U ɸ U q0 )
= 0 closure q0
= { q 0 q1 q2}
/’(q1 , a) = 0 closure(/(/
^
(q1,0),a))
/’(q1 , a) = 0 closure(/(0 closure q1 ),a))
= 0 closure(/({ q1 q2 } ,a) )
= 0 closure(/(q1 ,a)U /(q2 ,a) )
= 0 closure( q1 U ɸ )
= 0 closure q1
= { q 1 q2}
/’(q1 , b) = 0 closure(/(/
^
(q1,0),b))
/’(q1, b) = 0 closure(/(0 closure q1 ),b))
= 0 closure(/({ q1 q2 } ,b) )
= 0 closure(/(q1 ,b)U /(q2 ,b) )
=0 closure(ɸ U q0 )
=0 closure q0 = { q0 q1 q2}
/’(q2 , a) = 0 closure(/(/
^
(q2,0),a))
/’(q2, a) = 0 closure(/(0 closure q2 ),a))
= 0 closure(/({ q2 } ,a) )
= 0 closure q1
= { q 1 q2}
/’(q2 , b) = 0 closure(/(/
^
(q2,0),b))
/’(q2, b) = 0 closure(/(0 closure q2 ),b))
= 0 closure(/({ q2 } ,b) )
= 0 closure q0
= {q 0 q1 q2}

36. Theory of Computation 28

q
0

q
2

11
Start
a,b

a,b
q
1

a,b

a,b

a,b

a,b

b b
b
Transition of NFA
input
state
a b
q0

{ q1 q2}

{q0 q1 q2}

q1

{ q1 q2}

{q0 q1 q2}

q2

{ q1 q2}

{q0 q1 q2}


Transition diagram







/ ‘([q1 q2 ],a)= /(q1 ,a) U /(q2,a)
= { q1 , q2}U{ q1 , q2 }
=[ q1 , q2 ]
/ ‘([q1 q2 ],b)= /(q1 ,b) U /(q2,b)
= { q0 , q1 , q2}U{ q0 , q1 , q2 }
=[q0 , q1 , q2 ]
/ ‘([q0 q1 q2 ],a)= /(q0 ,a) U /(q1 ,a) U /(q2,a)
={ q1 , q2}U{ q1 , q2 }U{ q1 , q2 }
=[ q1 , q2 ]
/ ‘([q0 q1 q2 ],b)= /(q0 ,b) U /(q1 ,b) U /(q2,b)
={ q0 ,q1 , q2}U{ q0 ,q1 , q2 }U{ q0 ,q1 , q2 }
=[ q0 ,q1 , q2 ]
Transition table for DFA

37. Theory of Computation 29

[q1,q2,q3]
input
state
a b
q0

[ q1 q2 ]

[ q0 q1 q2 ]

q1

[ q1 q2 ]

[ q0 q1 q2 ]

q2

[ q1 q2 ]

[ q0 q1 q2 ]

q1 q2

[ q1 q2 ]

[ q0 q1 q2 ]

[ q0 q1 q2 ]

[ q1 q2 ]

[ q0 q1 q2 ]





a a b
a b b
b

a
a b





[q1,q2]

q0

q0 q1
q2

38. Theory of Computation 30

MINIMIZE METHOD
TABLE FILLING METHOD

/ (A,0)=B / (A,1)=F
/ (B,0)=G / (B,1)=C
/ (C,0)=A / (C,1)=C
/ (D,0)=C / (D,1)=G
/ (E,0)=H / (E,1)=F
/ (F,0)=C / (F,1)=G
/ (G,0)=G / (G,1)=E
/ (H,0)=G / (H,1)=C

TABLE 1
C is final state, It is distinguishable from other states.

B


C

X

X

D



X

E



X


F



X


G



X


H



X

A B C D E F G

39. Theory of Computation 31


TABLE 2

B

X

C

X

X

D

X



X

E



X


F

X



X


G

X

X


H


X


X


TABLE :3

B

X

C

X

X

D

X

X

X

E

X

X


F

X

X

X


G

X

X


H

X

X

A B C D E F G

40. Theory of Computation 32


TABLE :4

B

X

C

X

X

D

X

X

X

E

X

X

X

F

X

X

X

X

G

X

X

X


H

X

X
X
A B C D E F G

TABLE :5

B

X

C

X

X

D

X

X

X

E

X

X

X

F

X

X

X

X

G

X

X

X

X


H

X

X

X

X

A B C D E F G

41. Theory of Computation 33

TABLE :6

B

X

C

X

X

D

X

X

X

E

X

X

X

F

X

X

X

G

X

X

X

X

X

H

X

X

X

X

X

X
A B C D E F G
TABLE :7

B

X

C

X

X

D

X

X

X

E

X

X

X

F

X

X

X

X

G

X

X

X

X

X

X

H

X

X

X

X

X

X
A B C D E F G
Minimized DFA
State/Input 0 1
->A B D
B G C
C* A C
D C G
E G A

42. Theory of Computation 34

MINIMIZE METHOD [alter method]

&#3627409209;(A,0)=B /(A,1)=F
/(B,0)=G /(B,1)=C
/(C,0)=A /(C,1)=C
/(D,0)=C /(D,1)=G
/(E,0)=H /(E,1)=F
/(F,0)= C /(F,1)=G
/(G,0)=G /(G,1)=E
/(H,0)=G /(H,1)=c
Table 1
St\input 0 1
A B F
B G C
C A C
D C G
E H/B F
F C G
G G E
H G C

 B=H
Eliminate H
Replace H by B
Table 2
St/input 0 1
A B F
B G C
C A C
D C G
E B F
F C G
G G E/A
 A=E
Eliminate E
Replace E by A

43. Theory of Computation 35

A

B

G

D

c
Table 3
St\input 0 1
A B F/D
B G C
C A C
D C G
F C G
G G A
 D=F
Eliminate F
Replace F with D

Table 4
St\input 0 1
A B D
B G C
C A C
D C G
G G A

: This is the minimized DFA




0


0

1 1 0 1 1
0
1

0

44. Theory of Computation 36

THEOREM: Let L be a set accepted by Nondeterministic finite automata (NFA), then there
exist a Deterministic finite automata (DFA) that accepts L.
Proof:
Let M = (Q, Σ, /, qo, F) be an NFA for language L, then Define DFA Mʹ such that
Mʹ = (Qʹ, Σʹ, /ʹ, qoʹ, Fʹ)
(i) The states of Mʹ are all the subsets of M then the Qʹ=2
Q
(ii) The input symbols are common for both NFA and DFA. i.e., Σʹ = Σ
(iii) If q0 is the initial state in the NFA, then q0ʹ = [q0] = initial state in DFA

(iv) Fʹ be the set of all final states which contain final states of M. i.e., Fʹ ⊆ 2
Q
∪ F
(v) The element in Qʹ will be denoted by [q1, q2, q3, … , qi] is a single state in Qʹ and the
elements in Q denoted by{q1, q2, q3, …, qi} are multiple states in Q. Define /ʹ such that
/ʹ([q1, q2, q3, …, qi], a) = [p1, p2, p3, …, pj] iff /ʹ({q1, q2, q3, …, qi}, a) = {p1, p2, p3, …, pj}
This mean that in NFA, at the current states { q1, q2, q3, …, qi }, if we give input a
then it goes to the next states {p1, p2, p3, … , pj}.
While constructing DFA, the current state is assumed to be [q1, q2, q3, …, qi] with
input a, the next state is assumed to be [p1, p2, p3, … , pj].
On applying / function on each of states q1, q2, q3, …, qi, the new states may be any
of the states from p1, p2, p3, … , pj.
The theorem can be proved by mathematical induction on length of the input string x.
/?(q0ʹ, x) = [q1, q2, q3, …, qi] if and only if /(q0, x) = {q1, q2, q3, …, qi}
Basis: If the length of input string is 0, i.e., |x|=0, that means x is 0 then q0ʹ = [q0]
Induction: If we assume that the hypothesis is true for the input string of length I (or less
than I), then if xa is the string of length I + s.
Now the function /ʹ can be written as /ʹ(q0ʹ, xa) = /ʹ(/ʹ(q0, x), a)
By the induction hypothesis,
/ʹ(q0ʹ, x) = [p1, p2, p3, … , pj] if and only if /(q0, x) = {p1, p2, p3, … , pj}
By definition of /ʹ
/ʹ([p1, p2, … , pj], a) = [r1, r2, ..., rk] if and only if /({p1, p2, … , pj}, a) = {r1, r2, ..., rk}
Thus, /ʹ(q0ʹ, xa) = [r1, r2, ..., rk] if and only if /(q0, xa) = {r1, r2, ..., rk} is shown by induction.
Therefore L(M)=L(Mʹ).
i.e., If a language is accepted by NFA then the same language is also accepted by DFA.
Hence the theorem∎

THEOREM: If L is accepted by NFA with 0 transition, then their exist L which is accepted
by NFA without 0 transition. (Show that the language L accepted by NFA with 0 move must
be accepted by NFA without 0 move.)
Proof:
Let M = (Q, Σ, /, q0, F) be an NFA with 0 transition.
Construct Mʹ = (Q, Σ, /ʹ, q0, Fʹ)
where Fʹ={ F ∪{q0} if 0 closure contains state off
{ F otherwise
Mʹ is a NFA without 0 moves. The /ʹ function can be denoted by the /ʹʹ with same input.
For example, /ʹ(q, a) = /ʹʹ(q, a) for some q in Q and a from Σ.
We will apply the method of induction with input string x.
Basis:
The x will not be 0 because /ʹ(q0, 0)={q0} and /ʹʹ(q0, 0) = 0-closure(q0)
Assume that the length of string x to be 1, i.e., |x|=1, then x is a symbol, say ʹaʹ.
/ʹ(q0, a) = /ʹʹ(q0, a)
Induction
Assume that the length of string x to be more than 1. i.e., |x| >1.

45. Theory of Computation 37

Let w = xa
/ʹ(q0, wa) = /ʹ(/ʹ(q0, w), a)
By Induction hypothesis,
/ʹ(q0, w) = /ʹʹ(q0, w) = P
Now we will show that /ʹ(p, a) = /(q0,wa)
But /ʹ(p, a) = ∪
q in P /ʹ(q, a) = ∪
q in P /ʹʹ(q, a)
AS P = /ʹʹ(q0, w)
We have ∪
q in P /ʹʹ(q, a)= /ʹʹ(q0,wa)
Thus by define of /ʹʹ, /ʹ(q0, wa) = /ʹʹ(q0,wa)
L(M)=Lʹ(M)
i.e., If a language is accepted by NFA with 0 transition then the same language is also
accepted by NFA without 0 transition.
Hence the theorem∎


REGULAR EXPRESSION:
DEFENITION:
The language accepted by finite automata are easily described by simple
expression called regular expression.
REGULAR SET:
Regular sets are the sets which are accepted by finite automata.
EXACT DEFENITION:
Let ∑ be an alphabet which is used to denote the input set. The regular
expression over ∑ can be defined as follows
1) Фis the regular expression which denotes the empty set.
2) ξ is the regular expression and denote the set {ξ} (null string).
3) For each a in ∑ ,a is a regular expression and denote the set{a}.
4) If ‘R’ and ‘S’ are regular expression denoting the languages L1 and L2
respectively then
r+s is equivalent to L1υL2 ie.union
rs is equivalent to L1L2 ie.concatenation
r
*
equivalent to L1
*
ie.klean closure

EXAMPLE 1: write the regular expression for the language accepting all combination of a’s
over the set ∑={a}.
Solution:
Regular set={ ξ,a,aa,aaa,…….}
Regular expression(RE)=a*

EXAMPLE 2: design the RE for the language accepting all combination all combination of
a’s except the null q string over ∑={a}
Solution:
Regular set={ a,aa,aaa,………}
Regular expression(RE)=a+

EXAMPLE 3: design the RE for the language containing any no of a’s and b’s.
Solution:
Regular set={ ξ,a,b,aa,ab,bb,ba,aaa…………}

46. Theory of Computation 38

Regular expression(RE)=(a+b)
*


EXAMPLE 4: construct RE for the language accepting all the strings which are ending with
00 ∑={0,1}.
Solution:
Regular set={ 00,000,100,0000,0100,1000,1100……….}
Regular expression(RE)=(0+1)*00

EXAMPLE 5: write the RE for the language accepting the strings which are starting with 1
and ending with 0 ∑={0,1}
Solution:
Regular set={ 10,100,110,1000,1010,1100,1110………..}
Regular expression(RE)=1(0+1)
*
0

EXAMPLE 6: write RE to denote the language which accepts all the string which begin or
end with with either 00 or 11.
Solution:
L1=string begin with 00 or 11
L1=(00+11)(0+1)*
L2=string end with 00 or 11
L2 =(0+1)
*
(00+11)
RE=(00+11)(0+1)*+(0+1)
*
(00+11)

EXAMPLE 7: construct a RE for the language L which accepts all strings with atlest two ‘b’
over ∑={a.b}.
Solution:
RE=(a+b)
*
b(a+b)*b(a+b)*

EXAMPLE 8:Construct RE for the language which accepts all the string with atleast two b
over ∑={a,b,c}
Solution:
` RE=(a+b+c)
*
b(a+b+c)*b(a+b+c)*

EXAMPLE 9:construct a RE for the language which consist of exactly 2b’s over the set
∑={a,b}
Solution:
RE=a*ba*ba*



EXAMPLE10:construct a RE for the language L,∑={a.b} in which total no of a’s are
divisible by 3
Solution:
RE=(b*ab*ab*ab*)*

METHOD FOR CONSTRUCTION OF NFA FROM RE:
EXAMPLE1:Construct NFA for the RE b+ba*
Sol:
r=b+ba*
r=r?+r?

47. Theory of Computation 39

r?=b
r?=r?r?
r?=b
r?=a*
step1:
r?=b


EXAMPLE2: Construct an NFA for the given RE (01+2*)1
Sol:
R=(01+2*)1
R=r?r?
r?=01+2*
r?=1
r?=r?+r?
r?=01
r?=2*
step1:
r4=2*


Step2:
R3=01

Step3:
R2=1

Step4: 01+2*

48. Theory of Computation 40


Step5:(01+2*)1


DIRECT OR SUBSET METHOD:
EXAMPLE 1: design FA for the RE 10+(0+11)0*1
Step1:

Step2:

Step3:

49. Theory of Computation 41


Step4:

Step5:

Step6:

Step7:

50. Theory of Computation 42


EXAMPLE 2:design the DFA for the FE 0+01*
Step1:

Step2:

Step3:

EXAMPLE3:design DFA for the given RE
Step1:

Step2:

51. Theory of Computation 43


Step3:

Step4:

IDENTITY RULES FOR RE:
1.ξ.R=R.ξ=R
2.ξ

*=ξ
3.(Ф)*=ξ
4.Ф.R=R.Ф=Ф
5.Ф+R=R
6.R+R=R
7.RR* =R*R=R
+
8.(R*)*=R*
9.ξ+RR*=R
+
10.(P+Q)R=PQ+PR
11.(P+Q)*=P*Q*=(P*+*Q)*
12.R*(ξ+R)=(ξ+R)R*=R*
13.(R+ξ)*=R*
14.ξ+R*=R*
15.(PQ)*P=P(QP)*
16.R*R+R=R*R
AVDEN METHOD FOR CONVERTING DFA TO REGULAR EXPRESSION:
Step1: let q1 be the initial state.

52. Theory of Computation 44

Step2: there areq2,q3,……..qn no of states, the final state may be qj where j≤n.
Step3:let αji represents the transition from qj to qi.
Step4:calculate qi Є qi=αji.qij.
If qi is the start state then qi=αji.qj+ξ.
Step5:similarly compute the final state which ultimately gives the regular expression R.
R=Q+P then R=QP
*

EXAMPLE1: construct the RE for the given DFA

Solution:
q1=ξ+q1a 1
q2=q1b+q2d 2
consider q1=ξ+q1a
q1=ξa*
q1= a*
consider q2=q1b+q2b
sub q1= a* =>q2= a*b+q2b
q2= a*b+ b*
q2= a*b
+
RE= a*b
+

EXAMPLE2: construct RE for the DFA given below

Solution:
q1=ξ+q30+q10 1
q2= q 11+q21+ q31 2
q3= q 20 3
sub q3 in q2
q2= q11+q21+ q31
q2= q11+q2(1+01)
q2= q11(1+01)
*
4
sub 3 in 4
q1=ξ+ q200+q10 5
sub 4 in 5

53. Theory of Computation 45

q1=ξ+ q11(1+01)
*
00+ q10
q1=ξ+ q1(0+1(1+01)
*
00)
q1=ξ+(0+1(1+01)
*
00)
*

q1=(0+1(1+01)
*
00)
*
(ξ.R=R.ξ=R)


EXAMPLE3: construct the RE for the given DFA
Solution:
Refer example 1
Since q2 is the final state its enough to find q2 only and q3 is not the final state
USING DIRECT METHOD:
Construct RE for the given DFA

Step1:
K=0

r11 ξ
r12 0
r21

Ф
r22

ξ
Step2:
ri
k
j=(ri
k-1
k) (rk
k-1
k)
*
(rk
k-1
j)+ ri
k-1
j
K=1
(r1
1
1) i=1,j=1

(r1
1
1)= (r1
0
1) (r1
0
1)
*
(r1
o
1)+ r1
0
1
=(ξ)(ξ)
*
(ξ)+ξ
=ξ+ξ
= ξ
(r1
1
2) i=1,j=2

(r1
1
2)= (r1
0
1) (r1
0
1)
*
(r1
o
2)+ r1
0
2
=ξ+0+0
=0
(r2
1
1) i=2,j=1

(r2
1
1)= (r2
0
1) (r1
0
1)
*
(r1
o
1)+ r2
0
1
=Ф.ξ.ξ+Ф
=Ф

(r2
1
2) i=2,j=2

(r2
1
2)= (r2
0
1) (r1
0
1)
*
(r1
o
2)+ r2
0
2
=Ф(ξ)
*
.0+(1+ξ)
=Ф+ξ

54. Theory of Computation 46

=ξ

Step3:
Compute and find state from state q1 to final state q2
K=2
(r1
2
2)= (r1
0
2) (r2
0
2)*(r2
o
2)+ r1
0
2
=0(ξ)*ξ+0
=0+0
r12=0

55. Theory of Computation 47

Theorem: Every language defined by a regular expression is also defined by a finite
automaton.
Proof: Suppose L = L(R) for a regular expression R. We show that L = L(E) for some 0-NFA
E with:
1. Exactly one accepting state.
2. No arcs into the initial state.
3. No arcs out of the accepting state.
BASIS: There are three parts to the basis as shown in the following three figures.
Part (a) to handle the expression 0. The language of the automaton is easily seen to be {0},
since the only path from the start state to an accepting state is labeled 0. i.e., Regular
expression = 0.

Part (b) shows the construction for ϕ. Clearly there are no paths from start state to accepting
state, so ϕ is the language of this automaton. i.e., Regular expression = ϕ.


Finally, part (c) gives the automaton for a regular expression a. The language of this
automaton evidently consists of the one length string a, which is also L(a). i.e., Regular
expression = a.

It is easy to check that these automata all satisfy conditions (1), (2), and (3) of the inductive
hypothesis.

INDUCTION: We assume that the statement of the theorem is true for the immediate sub-
expressions of a given regular expression; that is, the languages of these sub-expressions are
also the languages of 0-NFA's with a single accepting state. The four cases are:
1. The expression is R + S for some smaller expressions R and S. Then the automaton of
Figure serves. That is, starting at the new start state, we can go to the start state of
either the automaton for R or the automaton for S. We then reach the accepting state of
one of these automata, following a path labeled by some string in L(R) or L(S),
respectively. Once we reach the accepting state of the automaton for R or S, we can
follow one of the 0-arcs to the accepting state of the new automaton.

Thus, the language of the automaton in Figure is L(R) U L(S).
0
R
S
0
0
0
a
0

56. Theory of Computation 48

2. The expression is RS for some smaller expressions R and S. The automaton for the
concatenation is shown in Figure. Note that the start state of the first automaton
becomes the start state of the whole, and the accepting state of the second automaton
becomes the accepting state of the whole. The idea is that the only paths from start to
accepting state go first through the automaton for R, where it must follow a path
labeled by a string in L(R), and then through the automaton for S, where it follows a
path labeled by a string in L(S).

Thus, the paths in the automaton of Figure are all and only those labeled by
strings in L(R)L(S).
3. The expression is R* for some smaller expression R. Then we use the automaton of
Figure. That automaton allows us to go either:

(a) Directly from the start state to the accepting state along a path labeled ε. That
path lets us accept 0, which is in L(R)* no matter what expression R is.
(b) To the start state of the automaton for R, through that automaton one or more
times, and then to the accepting state. This set of paths allows us to accept
strings in L(R), L(R)L(R), L(R)L(R)L(R), and so on, thus covering all strings in
L(R) except perhaps ε, which was covered by the direct arc to the accepting state
mentioned in the figure.
4. The expression is (R) for some smaller expression R. The automaton for R also serves
as the automaton for (R), since the parentheses do not change the language defined by
the expression.
It is a simple observation that the constructed automata satisfy the 3 conditions given in the
inductive hypothesis - one accepting state, with no arcs into the initial state or out of the
accepting state. ∎


ε
R
ε
ε
ε
ε
R S

57. Theory of Computation 49

PUMPING LEMMA: To prove languages are not regular.
Statement: Let L be a regular language, then there is a constant ɸ such that for every string S
in L and |S| R J. We can break S into three sub-strings and represented as S = TUV such
that
1. U ≠ &#3627409174;. i.e., |U| R s.
2. |TU| Q J.
3. For all G R r, the string TU
?
V is also in L.
Proof:
If L is a regular Language, then it is accepted by a DFA &#3627408436; = :&#3627408452;, &#3627409140;, &#3627409151;, M
4, &#3627408441;; with n
states. i.e., L = L(A). Consider the input string w of length ɸ or more, say S = &#3627408462;
5&#3627408462;
6. . . &#3627408462;
?
where I R J and each &#3627408462;
? is an input symbol. The mapping function / can be defined as
?:L
4, &#3627408462;
5&#3627408462;
6. . . &#3627408462;
?; = L
?.

For the string S of length m, this is more than the number of states n. By pigeonhole
principle, at least one state must repeat. Thus we can find two different integers E and F with
r Q E < F Q J such that L
?= L
?. Now we break S = TUV as follows:
1. T = &#3627408462;
5&#3627408462;
6… &#3627408462;
?
2. U = &#3627408462;
?+5&#3627408462;
?+6… &#3627408462;
?
3. V = &#3627408462;
?+5&#3627408462;
?+6… &#3627408462;
?
In the DFA &#3627408436; as shown in figure, we can move from the start state p0 to pi with the
input string T, U takes us from L
? back to L
? (since L
?= L
?), and V takes us from L
? to L
?.

Note that T may be empty if E = r, Also V may be empty if F = J = I. However U
cannot be empty as E < F.
?:L
4, &#3627408462;
5&#3627408462;
6. . . &#3627408462;
?&#3627408462;
?+5… &#3627408462;
?&#3627408462;
?+5… &#3627408462;
?; = ?:?:L
4, &#3627408462;
5, … , &#3627408462;
?;, &#3627408462;
?+5… &#3627408462;
?&#3627408462;
?+5… &#3627408462;
?;
= ?:L
?, &#3627408462;
?+5… &#3627408462;
?&#3627408462;
?+5… &#3627408462;
?;
= ?:?:L
?, &#3627408462;
?+5… &#3627408462;
?;, &#3627408462;
?+5… &#3627408462;
?;
= ?:L
?, &#3627408462;
?+5… &#3627408462;
?;
= M
?
If the automaton &#3627408436; receives the input w. that is TU
?
V.
Case 1: If G =0, then S = TU
0
V =TV. The automaton &#3627408436; goes from the start state L
0 to L
? on
input T. Since L
? is also L
?, A goes from L
? to the accepting state L
? on input V. Thus
&#3627408436; accepts TV.
Case 2: If G >0, then the automaton &#3627408436; goes from L
0 to L
? on input T. Circles from L
? to L
? k
times on input U
?
, and then goes from L
? to the accepting state L
? on input V. Thus
&#3627408436; accepts TU
?
V.
Thus, for G R0, TU
?
V is accepted by a automaton &#3627408436;. That is, TU
?
V is in &#3627408447;.
i.e. We have proved that given string of any length can be accepted by Finite Automata by
pumping a substring. i.e., substring repeated as many times as we like and resulting string
may be accepted by Finite Automata. ∎

ADVANTAGES: Pumping lemma is used to check the given language is not regular or not.
p0 pi pF
Start T = &#3627408462;
5… &#3627408462;
?
U = &#3627408462;
?+5… &#3627408462;
?
V = &#3627408462;
?+5… &#3627408462;
?

58. Theory of Computation 50


EXAMPLE1:show that the set L={b
i2
} is not regular.
Solution:
To prove L=b
i2
is not regular
i=2 L=2 => L=b
4
=bbbb
i=3 L=3 => L=b
9
=bbbbbbbbb
according to pumping lemma
Lu
i
w Є L where i≥1
L=uv
i
w
L=b(bb)
i
b if i=2 => bbbbbb not belongs to L

If i=3 => bbbbbbbb not belongs to L

EXAMPLE2: show that the language L={0
n
1
n+1
/n>0} is not regular
Solution:
To prove L={0
n
1
n+1
/n>0} is not regular
Let n=1 L=0
1
1
2
=

011
Let n=2 L=0
2
1
3
=00111
Let n=3 L=0
3
1
4
=0001111
Length of the string =n+n+1
=2
n
+1
Then according to pumping lemma
L=011
U=0 v=1 w=1
uv
i
w=01
i
1
=0111(if i=2)not belongs to L
e length of the string after pumping is not in 2
n
+1 form

EXAMPLE3: check the given language L={0
2n
/n/n≥1} is not regular or not
Solution:
Let n=1 L= 0
2(1)
=00

Let n=2

L =0
2(2)
=0000

Let n=3

L=0
2(3)
=000000
Note:
L=string consisting of even no of 0’s
L=even length of string with 0
Then according to pumping lemma
L= 0000
uv
i
w= o(00)
i
0
=0000(if n=1)
0(00)
i
0 Є L

59. Theory of Computation 51

Closure properties of regular languages (RL)
If certain languages are regular and a new language L is formed from them by certain
operations (such as union or concatenation) then L is also regular. These properties are called
closure properties of regular languages. Such languages represent the class of regular
languages which is closed under the certain operations. The closure properties express the
idea that when one or many languages are regular then certain related languages are also
regular. The closure properties of regular languages are as given below.
1. The union of two regular languages is regular.
2. The intersection of two regular languages is regular.
3. The complement of a regular language is regular.
4. The difference of two regular languages is regular.
5. The reversal of a regular language is regular.
6. The Kleene closure operation on a regular language is regular.
7. The concatenation of regular language is regular.
8. A homomorphism of regular languages is regular.
9. The inverse homomorphism of regular language is regular.

Theorem 1: If L1 and L2 are two languages then L1 ∪ L2 is regular.
Proof: If L1 and L2 are regular then they have regular expression L1 = L (R1) and L2 = L
(R2). Then L1 ∪ L2 = L (R1 + R2) thus we get L1 ∪ L2 as regular language. (Any language
given by some regular expression is regular).

Theorem 2: The complement of regular language is regular.
Proof: Consider L1 be regular language which is accepted by a DFA M = (Q, Σ, /, q0, F). The
complement of regular language L̅
1 is which is accepted by M ' = (Q, Σ, /, q0, Q-F). That
means M is a DFA with final states ∈ F and M ' is a DFA in which all the non-final states of
M become final. In other words, we can say that strings that are accepted by M are rejected
by M' similarly, the strings rejected by M are accepted by M'.
Thus L̅
1 is accepted by M' is regular.

Theorem 3: If L1 and L2 are two languages then L1 ∩ L2 is regular.
Proof: Consider that languages L1 is regular. That means there exists some DFA M1 that
accepts L1. We can write M1 = (Q1, Σ, /1, q1, F1 ) Similarly being L2 regular there is another
DFA M2 = = (Q2, Σ, /2, q2, F2 ).
Let L be the language obtained from L1 ∩ L2. We can the simulate M=(Q, Σ, /, q, F ).
Where Q = Q1 ∩ Q2
/ = /1 ∩ /2 a mapping function derived from both the DFAs.
q ∈ Q which is initial state of machine M.
F = F1 ∩ F2, the set of final states, which is common for M1 and M2 both. It is clear
that there exists some DFA which accepts L1 ∩ L2 i.e. L. Hence L is a regular language. This
proves that if L1 and L2 are two regular languages then L1 ∩ L2 is regular. In other words the
regular language is closed under intersection.
Theorem 4: If L1 and L2 are two regular languages then L1 - L2 is regular.
Proof : The L1 - L2 can also be denoted as L1 ∪ L̅
2
Consider L1 be regular language which is accepted by DFA M = (Q, Σ, /, q0, F). The
complement of regular language L1 is L̅
2 which is accepted by M ' = (Q, Σ, /, q0, Q-F). That
means M is a DFA with final states set F and M' is a DFA in which all the non final states of
M become final states and all the final states of M become non-final states Thus L1 and L̅
2
are two regular languages. That also means: these languages are accepted by regular
expressions. If L1 =L(R1) and L̅
2=L(R'2). Then L1 ∪ L̅
2 = L(R1+R'2). This ultimately shows

60. Theory of Computation 52

that L1 ∪ L̅
2 is regular. In other words L1 - L2 is regular. Thus regular languages are closed
under difference.

Theorem 5: The reversal of a regular languages is regular
Proof: Reversal of a string means obtaining a string which is written from backward that is
W
R
is denoted as reversal of string w. That means L(w
R
) = (L(w))
R
. This proof can be done
with basis of induction.
Basis: If w = ɛ or ϕ then w
R
is also ɛ or ϕ
i.e. (ɛ )
R
= ɛ and (ϕ )
R
= ϕ Hence L(w
R
) is also regular.
Induction :
Case 1: If w = w1 + w2 then w = (w1)
R
+( w2)
R

As the regular language is closed under union, w is also regular.
Case 2 : If w = w 1 w2 then w = (w1)
R
( w2)
R

As the regular language is closed under concatenation, w is also regular
Thus, the reversal of a regular languages is regular.

Theorem 6: The closure operation on regular language is regular
Proof : If language L1 is regular then it can be expressed as L1 =L(R1
*
). Thus for a closure
operation a language can be expressed as a language of regular expressions. Hence L1 is said
to be a regular language.

Theorem 7: If L1 and L2 are two languages then L1· L2 is regular. In other words regular
languages are closed under concatenation.
Proof: If L1 and L2 are regular then they can be expressed as L1 =L(R1) and L2 =L(R2), Then
L1.L2 =L(R1· R2) thus we get a regular language. Hence it is proved that regular languages are
closed under concatenation.

Theorem 8: A homomorphism of regular language is regular.
Proof : The term homomorphism means substitution of string by some other symbols. For
instance the string "aabb" can be written as 0011 under homomorphism. Clearly here, a is
replaced by 0 and b is replaced by 1. Let Σ is the set of input alphabets and Γ be the set of
substitution symbols then Σ *→Γ* is homomorphism. The definition of homomorphism can
be extended as
Let, w = a1 a2 … an
h(w) = h(a1)h(a2)...h(an)
If L is a Language that belongs to the set Σ, then homomorphic image of L can be defined as
h(L) = { h(w): w ∈L }
To prove that if L is regular, h(L) is also regular consider following example
Let Σ = {a,b} and w = abab
Put h(a) = 00 and h(b) = 11
Then we can write h(w) = h(a) h(b) h(a) h(b) =00110011
The homomorphism to language is applied by applying homomorphism on each string
of language.
∴ If L = ab
*
b = ab
+
= {ab, abb, abbb, abbbb, ...}
Now h(L) = {0011, 001111, 00111111, 0011111111, ...}
∴ h(L) = 00 (11)
+

As it can be represented by a regular expression, it is a regular language. Hence it is
proved that if L is regular then h(L) is also regular. In other words, family of regular
languages is closed under homomorphism.

61. Theory of Computation 53

Theorem 9: The inverse homomorphism of regular language is regular.
Proof: Let h: Σ*→Γ* is homomorphism.
The Σ is the input set and Γ be the substitution symbols used by homomorphic function.
Let, L be the regular language where L∈ Σ then h(L) be homomorphic language.
The inverse homomorphic language can be represented as h
-1
(L) such that h
-1
: Γ* → Σ*
Let, h
-1
(L) = {w | w ∈ L}
If L is regular then h(L) is also regular because regular language is closed under
homomorphism. That if there exist a FA M = (Q, Σ, /, q, F) which accepts L then h(L) must
also be accepted by FA M. For complement of L i.e. language L' the inverse homomorphic
language is h
-1
(L). Let M' = (Q, Σ, /, q, Q-F) be the FA in which all the final states of M
become non-final states and all the non-final states of M become the final states. Clearly the
language L' can be accepted by M' Hence h
-1
(L) must also be accepted by FA M'.
Let L= (010)* is a R.L., h(0) = a and h(1) = bb be a homomorphic function then h(L) =
(abba)*
h
-1
(h(L))= (010)* = L as the inverse homomorphism h
-1
(a)=0 and h
-1
(bb)=1.

Decision properties of regular languages (RL)
1. Membership property: A string is in a language, i.e., w ∈ L
2. Emptiness property: Accepting state separated from start state, i.e., ɸ
3. Equivalence property: Two languages are equal, i.e., L1 = L2