Monday (11:00am--11:55am), Wednesday (10:00am--10:55am) and Thursday (09:00am--09:55am)
Venue
A-LH-2
Syllabus
Alphabets, languages, finite state machines.
Deterministic and non-deterministic finite automata, regular languages, regular expressions, pumping lemma for regular languages, Myhill-Nerode theorem.
Context free grammars, context free languages, parse trees, Chomsky normal form, push down automata, pumping lemma for CFLs and applications.
Turing machines, variants, decidable and recognizable languages, undecidability theory, undecidability of the Halting problem, many-one reductions, Rice’s theorem.
Time and space bounded computation, class P, theory of NP completeness, polynomial time reductions, introduction to space complexity, classes L, NL, PSPACE.
Evaluations
Timed-exams in class (at least 4; roughly at the end of each month).
Textbooks and References
Michael Sipser, Introduction to the Theory of Computation.
John Hopcroft, Rajeev Motwani and Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation.
Dexter Kozen, Automata and Computability.
Lectures
Lectures 1-2: General information, alphabet, strings, finite state automata, regular languages.
Lecture 3: More examples of regular languages.
Lecture 4: Regular operations, regular expressions and regular languages.