- Deterministic Finite Automata
- Non-Deterministic Finite Automata
- Finite Automata with Epsilon-Transitions
- Formal Notation for Epsilon-NFAs
- Epsilon-Closure
- Extended Transistions and Languages for Epsilon-NFAs
- Eliminating Epsilon-Transitions
- Finite Automata and Regular Expressions
- Algebraic Laws of Regular Expressions
- The Pumping Lemma
- Closure Properties of Regular Languages
- Context-Free Grammars
- Definition
- Parse Trees
- Ambiguity in Grammars and Languages
- Pushdown Automata
- Definition
- Languages of PDA
- Context-Free Languages Equivalence of PDAs and CFGs
- Chomsky Normal Form for Context-Free Grammars
- Closure Properties of Context-Free Languages
- Decision Problems for CFLs
- Turing Machines
- Definition
- Undecidability
- Undecidable Problems about Turing Machines
- Post's Correspondence Problem
- Intractable Problems
- P and NP Classes
- The SAT problem
- Restricted SAT problems
- Independent Sets
- Directed Hamiltonian-Circuit
- Undirected Hamiltonian-Circuit
- Traveling Salesman Problem
support companion site
