Computability & Formal Lang Th.

Catalog description

Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. Halting problems, undecidable problems, recursive functions, Chomsky hierarchy, Church’s thesis and the limits of computability. Proofs of program properties including correctness. Prerequisite: CSCI 281 Discrete Structures 3 semester hours.