Theory of Computation

Catalog description

This course introduces the theory of computability, including important results from the study of automata and formal languages. Includes introductory material about the theory of directed graphs and trees. A discussion of automata and their relationship to regular, context free and context-sensitive languages. General theories of computability, including Turing machines, and recursive functions. Further topics include decidability, undecidability and computational complexity. 3 Lecture hours. Prerequisite: MA 306. Offered: Spring, even years.