COL352
| COL352 | |
|---|---|
| Introduction to Automata & Theory of | |
| Credits | 3 |
| Structure | 3-0-0 |
| Pre-requisites | COL202 |
| Overlaps | |
COL352 : Introduction to Automata & Theory of
Regular Languages, Finite Automata, equivalence, minimization, Myhill-Nerode Theorem, introduction to non-determinism, Context free grammars, Pushdown automata, equivalence and applications. Turing machines, Recursive and Recursively enumerable sets, non-determinism, RAMs and equivalence, Universal Turing Machines, undecidability, Rice's theorems for RE sets, Post machines, Basics of Recursive function theory. Equivalence, Church's thesis, computational complexity, space and time complexity of Turing Machines, Relationships, Savage's theorem, Complexity classes, Complete problems, NP-completeness, Cook-Levin theorem.