MATH 552 Formal Languages and the Theory of Computation
Languages and their representation, finite automata and regular grammars, pushdown automata and context-free languages. Turing machines; the halting problem, linear bounded automata and context-sensitive languages; relations between formal languages and recursive sets, time and tape bounds on Turing machines, deterministic pushdown automata. Prerequisite: 551.