CS 575 Theory of Computation

This is a course on the theory of computing. Topics covered include finite automata, regular expressions and languages, pushdown automata, pumping lemmas for regular and context-free grammars, the Chomsky hierarchy of language classes, Turing machines and computability, the decidability of the halting problem, time complexity and NP-completeness and tractability.

Credits

3

Prerequisite

(CS 472 or equivalent) or Permission of Instructor