CSS.204.1 Automata and Computability

Instructor: 

Semester: 

  • 2021 Autumn/Monsoon (Aug - Dec)
  • Regular languages, Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA), Equivalence of DFA and NFA, closure properties of regular languages, regular expressions, Pumping lemma for regular languages, Myhill Nerode theorem, collapsing nondeterministic automata through bisimulation, monadic second order (MSO) logic and its relation to regular languages
  • Context-free Languages and Pushdown Automata (PDA), Context-free grammar (CFG), Equivalence between CFG and PDA, Closure properties of context-free languages, Pumping Lemma for CFL, Deterministic pushdown automata
  • Turing machines, modifications of Turing machines, two stack and counter machines, recursive and recursively enumerable sets, undecidability, halting problem, reduction, Rice's theorem.

References:

  • John E. Hopcroft, Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.
  • Dexter C. Kozen. Automata and Computability. Springer, 1997.