C S 470 - Computability, Automata and Formal Languages

3 Credits

Finite automata and regular expressions, context-free grammars, context-free languages, and pushdown automata, Turning machines, undecidability, the Chomsky hierarchy of formal languages, computational complexity and intractable problems.Prerequisites: MATH 215 and MATH 313.
Meets with C S 570.