B501 | ALL | Leivant

3cr. 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.