Automata Theory: MATH 460 (3)
Theoretical models of computation. Finite automata—regular expressions, Kleene's theorem, regular and nonregular languages. Pushdown automata—context-free grammars, Chomsky normal form, parsing. Turing machines—the halting problem. NP-complete problems.
Prerequisite: MATH 221 or MATH 360.
| Hours | Topic |
|---|---|
| Finite Automata (12 hours) | |
| 2.0 | Regular expressions |
| 2.0 | Deterministic finite automata |
| 2.0 | Kleene's theorem |
| 2.0 | Nondeterministic finite automata |
| 2.0 | Regular and nonregular grammars |
| 2.0 | Decidability—the pumping lemma |
| Pushdown Automata (12 hours) | |
| 3.0 | Context-free grammars |
| 2.0 | Chomsky normal form |
| 3.0 | Pushdown automata |
| 2.0 | Parsing |
| 2.0 | Decidability |
| Turing Machines (9 hours) | |
| 3.0 | Turing machine models |
| 3.0 | Reduction |
| 3.0 | Decidability—the halting problem |
| Computational Complexity (2 hours) | |
| 2.0 | NP-complete problems |
Total: 35.0 hours, excluding holidays, review sessions, and exams
*Fifty-minute class hours close this window