CSCE 5400 - Formal Languages, Automata and Computability

3 hours

Deterministic and non-deterministic finite automata, regular expressions and sets, context-free grammars and pushdown automata. Turing machines as acceptors, enumerators and computers. Church’s thesis, universal Turing machines and the halting problem, the Chomsky hierarchy and intractable problems.

Prerequisite(s): None.