**CS3452
**

**THEORY
OF COMPUTATION**

** **

**COURSE
OBJECTIVES: **

•
To understand foundations of computation including automata theory

•
To construct models of regular expressions and languages.

•
To design context free grammar and push down automata

•
To understand Turing machines and their capability

•
To understand Undecidability and NP class problems

**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.

**UNIT
II REGULAR EXPRESSIONS AND LANGUAGES **

Regular
expression – Regular Languages- Equivalence of Finite Automata and regular
expressions – Proving languages to be
not regular (Pumping Lemma) – Closure properties of regular languages.

**UNIT
III CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA **

Types
of Grammar - Chomsky‘s hierarchy of languages -Context-Free Grammar (CFG)
and Languages – Derivations and Parse
trees – Ambiguity in grammars and languages – Push Down Automata (PDA): Definition – Moves -
Instantaneous descriptions -Languages of pushdown automata – Equivalence of pushdown automata
and CFG-CFG to PDA-PDA to CFG – Deterministic
Pushdown Automata.

**UNIT
IV NORMAL FORMS AND TURING MACHINES**

Normal
forms for CFG – Simplification of CFG- Chomsky Normal Form (CNF) and Greibach
Normal Form (GNF) – Pumping lemma for
CFL – Closure properties of Context Free Languages –Turing Machine : Basic model – definition and
representation – Instantaneous Description – Language acceptance by TM – TM as Computer of Integer
functions – Programming techniques for Turing
machines (subroutines).

**UNIT
V UNDECIDABILITY **

Unsolvable
Problems and Computable Functions –PCP-MPCP- Recursive and recursively enumerable languages – Properties - Universal
Turing machine -Tractable and Intractable problems - P and NP completeness –
Kruskal’s algorithm – Travelling Salesman Problem- 3-CNF SAT problems.

**COURSE
OUTCOMES: **

At
the end of this course, the students will be able to:

CO1:
Construct automata theory using Finite Automata

CO2:
Write regular expressions for any pattern

CO3:
Design context free grammar and Pushdown Automata

CO4:
Design Turing machine for computational functions

CO5:
Differentiate between decidable and undecidable problems

**TEXT
BOOKS: **

1.
Hopcroft J.E., Motwani R. & Ullman J.D., "Introduction to Automata
Theory, Languages and
Computations", 3rd Edition, Pearson Education, 2008.

2.
John C Martin , "Introduction to Languages and the Theory of
Computation", 4th Edition, Tata
McGraw Hill, 2011.

**REFERENCES:
**

1.
Harry R Lewis and Christos H Papadimitriou , "Elements of the Theory of
Computation", 2nd Edition, Prentice
Hall of India, 2015.

2.
Peter Linz, "An Introduction to Formal Language and Automata", 6th
Edition, Jones & Bartlett, 2016.

3.
K.L.P.Mishra and N.Chandrasekaran, “Theory of Computer Science: Automata
Languages and Computation”, 3rd Edition,
Prentice Hall of India, 2006.