Course Topics
An advanced, junior-year college-level course which teaches Automata Theory from relatedly simple finite automata to extremely hard NP-complete problems.
Topics include:
- Deterministic and nondeterministic automata, regular expressions, and the equivalence of these language-defining mechanisms
- Context-free grammars, recursively enumerable languages, and other languages, along with parse trees, closure properties, decision properties, and a pumping lemma for context-free languages
- Pushdown automata and their nondeterministic equivalence in language-defining power to context-free grammars
- Turing machines and their ability to model any computing device
- Intractable problems, which requires exponential computing time, and their subcategories, which include NP-hard and NP-complete problems like the Traveling Salesman Problem.
- Proofs, lemmas, and discussion of P=NP?
