||1.Introduction to Automata Theory, Languages and
Computation, by John. E. Hopcroft, Rajeev
Motwani, J. D. Ullman, published by Pearson
Education Asia, 2006.
2.Elements of the Theory of Computation, by H.R.
Lewis and C.H.Papadimitrou, published by Prentice
Hall Inc, 1981.
||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.