Course Details

1	Title of the course (L-T-P-C)	Automata theory (3-1-0-8)
2	Pre-requisite courses(s)	Exposure to Discrete Structures
3	Course content	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.
4	Texts/References	Introduction to Automata Theory, Languages and Computation, by John. E. Hopcroft, Rajeev Motwani, J. D. Ullman, 3rd edition. Pearson. 2013. Elements of the Theory of Computation, by H.R. Lewis and C. H. Papadimitrou, 2nd Edition. Prentice Hall Inc, 1998.

Academics Course