Mathematics (MATH)
School of Mathematics and Statistics
Faculty of Science
MATH 4805 [0.5 credit]
Theory of Automata (Honours)
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.)
Also offered at the graduate level, with additional or different requirements, as
MATH 5605, for which additional credit is precluded.
Prerequisite:
MATH 3805 or
MATH 3106 or
MATH 3158 (or
MATH 3100) or permission of the School.
Lectures three hours a week.