| Course Code | CS 310 |
| Course Name | Automata Theory |
| Offered to | UG/PG |
| Pre-requisites | NIL |
| Lecture | 3 |
| Tutorial | 0 |
| Practical | 0 |
| Credit | 6 |
| Reference | 1. Introduction to Automata Theory, Languages and Computation, by John. E. Hopcroft, Rajeev Motwani, J. D. Ullman, published by Pearson Education Asia, 2006. Full 2. Elements of the Theory of Computation, by H.R. Lewis and C.H.Papadimitrou, published by Prentice Hall Inc, 1981. |
| Description | Finite state machines (DFA/NFA/epsilon NFAs), regular expressions. Properties of regular languages. My hill-Nerode Theorem. Non-regularity. Push down automata. Properties of context-free languages. Turing machines:Turing hypothesis, Turing computability, Nondeterministic, multi tape and other versions of Turing machines. Church`s thesis, recursively enumerable sets and Turing computability. Universal Turing machines. Unsolvability, The halting problem, partial solvability, Turing enumerability, acceptability and decidability, unsolvable problems about Turing Machines. Post`s correspondence problem. |