Computability techniques

Learning Goal: Use the pumping lemma to prove that a given language is not regular.

PDF LaTeX Raw HTML

Learning Goal: Use diagonalization to prove that there are 'hard' languages relative to certain models of computation.

PDF LaTeX Raw HTML

Learning Goal: Use appropriate reduction (e.g. mapping, Turing, polynomial-time) to deduce the complexity of a language by comparing to the complexity of another.

PDF LaTeX Raw HTML