The course will essentially be a course on Theory of
- 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
- Turing machines and undecidability, including Rice's theorem and Godel's