CIS473 Automata and Computability (Fall)

Countable and uncountable sets; diagonalization proofs; finite state automata; regular, context-free, context-sensitive, recursive, and r. e. languages; Turing machines; relationships between classes of languages and machines; the halting problem; proof methods for decidability and undecidabilty.

Prereq: CIS 375 or MAT 375 (or equivalent abstract or discrete mathematics course)

Department: Computer and Information Science

Location: London

Semester: Fall

Credits: 3