Formal Models of Computation credit: 3 or

4 Hours

Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; linear-bounded automata and context-sensitive languages; computability and the halting problem; undecidable problems; recursive functions; Chomsky hierarchy; computational complexity. Same as MATH 475 . 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: CS 374 or ECE 374 .