Automata Computability and Formal Languages

Catalog description

The course introduces formal languages and automata theory through a programming-based approach. The course introduces regular languages, context-free languages, context-sensitive languages, and computability. Topics include finite state automata, regular expressions, and regular grammars; pushdown automata and context-free languages; context-sensitive grammars and Turing machines; determinism and nondeterminism; programming-based construction proofs, issues of complexity including P and NP; and computability issues including undecidable problems such as the halting problem and reduction proofs. The course includes individual programming assignments, team programming projects and a major team project that requires integration and application of knowledge and skills acquired in earlier course work. Course instruction covers the necessary mathematical foundations of automata and computational theory that are not covered by prior courses.