CS1013 THEORY OF COMPUTATION
Instructor
Place Email id Syllabus Study Materials Text Book |
Sharanya S
SRM University [email protected] syllabus.txt 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 |