Computer Science | Theory of Computing
B501 | 8255 | 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. B501
corresponds to old C451 and C452.