Computer Science (COMP)
School of Computer Science
Faculty of Science
COMP 4805 [0.5 credit]
Theory of Automata
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:
COMP 3805 or
MATH 3106 or
MATH 3158 (or
MATH 3100) or permission of the School.
Lectures three hours a week.