CPS 4501 FORMAL LANGUAGES AND AUTOMATA THEORY

Formal definitions of automata, including the finite automaton, the pushdown automaton, and the Turing Machine. Different types of formal languages and their relationships to automata. The Church-Turing Thesis and the notion of algorithm. Decidability and Solvability.