Embedded Files
Prerequisites
Discrete Mathematics
Data Structures
Syllabus
Finite Automata, Regular expressions, Regular languages, Deterministic and non- deterministic computations and their equivalence. Properties: closure, decidability, minimality of automata, Pumping Lemma for Regular languages.
Recursive and recursively enumerable sets models: Turing Machines, grammars, recursive functions, their equivalence, Post machines, Minskey’s theorem, Church-Turing Thesis, Properties: closure, decidability, undecidability/non-computability, notion of reductions.
Context free languages models: grammars, Pushdown automaton and their equivalences, Pumping Lemma for Context free languages, Properties: closure.
Suggested Readings:
J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata, Languages, and Computation (2nd edition), Pearson Edition, 2001.
Cohen, “Introduction to Computer Theory”, John Wiley.
M. 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.
Weekly Office Hours
FRI : 15:10 - 16:00 Hours
SAT : 15:10 - 16:00 Hours
Homeworks
Homework 1: Due Date: August 22, 2016.
Homework 2: Due Date:
Google Sites
Report abuse