| |
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.
|
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) |
Total: 35.0 hours, excluding holidays, review sessions, and exams
*Fifty-minute class hours
close this window
|
 |
