Embedded Files
Prerequisites
Discrete Mathematics
Syllabus
Finite automata; deterministic and non-deterministic. Acceptance of language by finite automata. Equivalence and minimization of finite automata. Moore and Mealy machines. Regular expressions. Grammars and Languages, Derivations, Language generated by a grammar. Regular Language and regular grammars. Pumping Lemma, Kleene’s theorem. The Chomsky hierarchy, Context-free and context-sensitive grammars and languages. Turing Machines: Basic definitions. Turing machines as language acceptors. Universal Turing machines. The halting problem.
Suggested Readings:
J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata, Languages, and Computation (2nd edition), Pearson Edition, 2001.
Daniel I.A. Cohen, Introduction to Computer Theory (2nd edition), John Wiley, 2007.
Michael Sipser, Introduction to Theory of Computation, PWS Publishing Corporation, 1997.
T.C. Martin, Theory of Computation, Tata McGraw-Hill.
H.R. Lewis, C.H. Papadimitrou, Elements of the Theory of Computation, PHI.
K.L.P. Mishra, N. Chandrasekaran, Theory of Computer Science: Automata, Languages and Computation, PHI.
Arindama Singh, Elements of Computation Theory (Texts in Computer Science), Springer, 2009.
Weekly Office Hours
THU : 16:10 - 17:00 Hours
SAT : 16:10 - 17:00 Hours
Homeworks
Homework 1: Due Date: ???.
Homework 2: Due Date: ???.
Google Sites
Report abuse