Skip Navigation

Natural Science Division

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