Computer Science | Theory of Computing
B501 | 1454 | Leivant


(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.