Finite automata and regular expressions, properties of regular sets, context-free grammars, pushdown automata, deterministic context-free languages. Turing machines, the Chomsky hierarchy. Undecidability, intractable problems. Also listed as COMP 4805. Prerequisite(s): MATH 3805 or MATH 3106 or MATH 3158 or permission of the School.Also offered at the graduate level, with different requirements, as MATH 5605, for which additional credit is precluded.Lectures three hours a week.
Finite automata and regular expressions, properties of regular sets, context-free grammars, pushdown automata, deterministic context-free languages. Turing machines, the Chomsky hierarchy. Undecidability, intractable problems. Also listed as COMP 4805. Prerequisite(s): MATH 3805 or MATH 3106 or MATH 3158 or permission of the School.Also offered at the graduate level, with different requirements, as MATH 5605, for which additional credit is precluded.Lectures three hours a week.