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 MATH 4805.Precludes additional credit for MATH 5605. Prerequisite(s): COMP 3805 or MATH 3106 or MATH 3158 (or MATH 3100) or permission of the School.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 MATH 4805.Precludes additional credit for MATH 5605. Prerequisite(s): COMP 3805 or MATH 3106 or MATH 3158 (or MATH 3100) or permission of the School.Lectures three hours a week.