Theory of Computation

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.