CS3452 Theory of Computation Syllabus - Anna University

CS3452 THEORY OF COMPUTATION

L T P C: 3 0 0 3

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 epsilon-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

TOTAL:45 PERIODS

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.