CS5001 – THEORY OF COMPUTATION

Anna University Tiruchirappalli - 620 024
Regulations 2007
Sylllabus
M.E. COMPUTER SCIENCE AND ENGINEERING ELECTIVES

CS5001 – THEORY OF COMPUTATION


UNIT I FINITE AUTOMATA AND REGULAR LANGUAGES 9

Finite Automata and Regular Languages – Regular Expressions and Regular Languages – Non
Determinism and Kleenes Theorem – Equivalence of DFA and NFA – Finite Automation with E–
moves – Equivalence of Regular Expression and NFA with E–moves – Pumping Lemma for Regular Sets.

UNIT II CONTEXT FREE LANGUAGES 9

Context Free Languages – Derivation and Languages – Relationship between Derivation and Derivation Trees – Simplification of Context Free Grammars – Normal Forms for Context Free
Grammars – CNF – GNF.

UNIT III PUSH DOWN AUTOMATA (PDA) 9
Acceptance by PDA – Pushdown Automata and Context Free Languages – Pumping Lemma for
CFL – Deterministic Context Free Languages and Deterministic Pushdown Automata.

UNIT IV TURING MACHINE 9

Context Sensitive Languages and LBA – Turing Machine (Definition And Examples) – Computable Languages and Functions – Church Turing Hypothesis – Universal Turing Machine – P and NP Problems – NP – Complete.

UNIT V UNSOLVABLE PROBLEMS 9

Unsolvable Problems – Rice Theorem – Post's Correspondence Problem – Recursive and Recursively Enumerable Languages.

Total: 45
TEXT BOOKS
1. Hopcroft and Ullman, “Introduction to Automata, Languages and Computation”, 2nd
Edition, Narosa Publishers, 2000.
2. John C. Martin, “Introduction to languages and the Theory of Computation”, 2nd Edition,
McGraw Hill, 1997.

REFERENCES
1. A. M. Natarajan, A. Tamilarasi & P. Balasubramani, “Theory of Computation”, New Age
International publishers, 2002.
2. K.L.P.Mishra, N.Chandrasekaran, “Theory of Computation”, 2nd Edition, EEE, Prentice Hall
of India, 1998.
3. Peter Linz, “An Introduction to formal languages and Automata”, Narosa Publishing House,
2001.
4. Harry R. Lewis, Christos H. Papadimitriou, “Elements of Theory of Computation”, Prentice
Hall, 2002.

FEEL USEFUL PLEASE GIVE +1