Computer Science | Theory of Computing
B501 | ALL | Leivant

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. B501
corresponds to old C451 and C452.