AUTOMATA THEORY

Catalog description

Formal languages (regular, context -free, recursive, and recursively enumerable), machine models (deterministic and non - deterministic finite automata, push -down automata, and Turing machines), grammars (regular, context -free, and unrestricted), relationship s between these concepts, the Church -Turing thesis, Rice’s theorem, and undecidability. Prerequisite: CSCI 152 with a grade of no less than a B. This course fulfills a MATH elective for mathematics majors and a PHYS elective for physics majors.