Automata Theory & Formal Lg.

Catalog description

Theory and application of automata and the languages they recognize. Regular languages, deterministic and non-deterministic finite automata, regular expressions, context-free languages, context-free grammars, pushdown automata, normal forms, context-sensitive languages, linear bounded automata, Turing recognizable languages, Turing decidable languages, Turing machines, computability, decidability, reducibility. Students utilize an automata simulator to program finite automata, pushdown automata, and Turing machines. Application of concepts. Prerequisites: CS 310 and either MATH 314 or MATH 330. All prerequisites must have a grade of C- or better. Offered every semester.