CS1013 THEORY OF COMPUTATION
UNIT I - FINITE AUTOMATA (9 hours)
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.
Download Unit 1 Notes
UNIT II - GRAMMARS (9 hours)
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.
Download Unit 2 Notes
UNIT III - PUSHDOWN AUTOMATA (9 hours)
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL - pumping lemma for CFL – problems based on pumping Lemma.
Download Unit 3 Notes
UNIT IV - TURING MACHINE (9 hours)
Turing Machines- Introduction – Formal definition of Turing machines – Instantaneous descriptions- Turing Machine as Acceptors – Turing Machine as Transducers Computable Languages and functions – Turing Machine constructions – Modifications of Turing Machines.
Download Unit 4 Notes
UNIT V - COMPUTATIONAL COMPLEXITY (9 hours)
Undecidability- Basic definitions- Decidable and undecidable problems - Properties of Recursive and Recursively enumerable languages – Introduction to Computational Complexity: Definitions-Time and Space complexity of TMs – complexity classes – introduction to NP-Hardness and NP-Completeness
Download Unit 5 Notes
Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory, Languages and Computations”, Third Edition, Pearson Education, 2008.
Download PDF Book