CSCI-2400

Models of Computation

This course introduces conceptual tools for reasoning about computational processes and the languages with which they are prescribed. It bears directly upon language translation, program verification, and computability. Topics to be covered include formal languages, finite automata, pushdown automata, nondeterminism, regular expressions, context-free grammars; parsing, compiler design basics; computability, Turing machines, Church’s thesis, unsolvability and intractability. Prerequisites: CSCI-2300 and MATH-2800. Fall and spring terms annually.

4 credit hours