CS 373 - Automata Theory & Formal Lg.

Credits: 4

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 will utilize an automata simulator to program finite automata, pushdown automata, and Turing machines. Application of concepts. Required activity includes student presentations. Prerequisites: Either CS 140 or CS 210 and either MATH 314 or MATH 330 (All prerequisites must have a grade of C- or better). Offered every semester.