Skip Navigation

2009-2010 Undergraduate Calendar

Main Links
Related Links


Link to class schedule

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.

Summer session: some of the courses listed in this Calendar are offered during the summer. Hours and scheduling for summer session courses will differ significantly from those reported in the fall/winter Calendar. To determine the scheduling and hours for summer session classes, consult the class schedule at

Not all courses listed are offered in a given year. For an up-to-date statement of course offerings for the current session and to determine the term of offering, consult the class schedule at

© 2021 Carleton University 1125 Colonel By Drive, Ottawa, ON, K1S 5B6 Canada | (613) 520-7400