CSCI 4325 Automata, Formal Languages, and Computability

The course presents formal computation models. Topics include finite state machine, pushdown state machine, Turing machine, halting problem, definition and properties of formal grammars and their languages as well as theory of computability and complexity including the complexity of optimization and approximation problems.