Automata and Computability

Catalog description

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.