CS6503 - THEORY OF COMPUTATION
UNIT I: FINITE AUTOMATA
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
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
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
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
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.
UNIT IV: TURING MACHINES
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
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.
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
tyle='font-size:13.5pt; color:black'>
