- Languages.
- Minimization.
- Eliminating useless variables from context-free grammars.
- Decidability. And for the philosophically inclined students also definability, for comparison.
- Grammars.
- Rice's theorem.
- The undecidability of the empty intersection problem and the ambiguity problem for context-free grammars.
- Computable (or recursive) and partial recursive functions.
- Complexity classes.
*n*-ary and*n*-adic representations of natural numbers.- The undecidability of first order logic.
- The undecidability of arithmetic, Goedels incompleteness theorem, and the class of arithmetical languages.