Theoretical Foundations of Computer Science

Catalog description

Topics include finite automata, regular languages, regular expressions, and regular grammars; pushdown automata and context-free languages; Turing machines; Church-Turing Thesis; the Halting Problem; undecidability; classes of languages, including the Chomsky hierarchy and the classes P, NP, and NP-Complete. Proof techniques for showing language (non)membership in a class.