COMPUTER SCIENCE THEORY

3.00 points · University catalogue

CC/GS: Partial Fulfillment of Science Requirement Corequisites: COMS W3134 , COMS W3136 , COMS W3137 Regular languages: deterministic and non-deterministic finite automata, regular expressions. Context-free languages: context-free grammars, push-down automata. Turing machines, the Chomsky hierarchy, and the Church-Turing thesis. Introduction to Complexity Theory and NP-Completeness.