CS 310 : Automata Theory
Course Code CS 310
Course Name Automata Theory
Offered to UG
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.