Course outline
The course will essentially be a course on Theory of
Computation.
- Finite-state automata, including the Myhill-Nerode theorem, ultimate
periodicity, and Buchi's logical characterization.
- Pushdown automata and Context-free languages, including
deterministic PDA's, Parikh's theorem, and the
Chomsky-Shutzenberger theorem.
- Turing machines and undecidability, including Rice's theorem and Godel's
incompleteness theorem.