Computer Science | Theory of Computing
B501 | ALL | Wise


B501 Theory of Computing (3 cr.) P: C241. Deterministic and
nondeterministic automata, regular expressions, pumping lemmas;
context-free languages, parsing, pushdown automata, context-sensitive
languages, LBA, LR(k) languages, closure and decidability of language
classes. Turing machines, random access machines, grammars, general
recursive functions, equivalence of computation models, universal
machines, relative computing. Unsolvability, semi-recursive sets,
Rice's Theorem. Space and time complexity, NP completeness. Credit not
given for both B501 and B401. B501 corresponds to old C451 and C452.