Mathematical Background

Strings, languages, relations, digraphs, inductive definitions, types of proof.

Finite Automata & Regular Expressions

DFA, NFA, regular expressions, Kleene’s Theorem.

Properties of Regular Sets

Pumping Lemma, closure properties, decision algorithms.

Context-Free Grammars & Languages

CFGs, regular grammars.

Simplified & Normal Forms

Useful symbols, unit productions, Chomsky normal form.

Pushdown Automata

PDA definition, equivalence of PDA and CFG.

Properties of Context-Free Languages

Pumping Lemma, closure properties, CYK algorithm.

Turing Machines

TMs, variants, undecidability of halting problem.

Undecidability

Decidability, undecidability proofs, reductions.