Skip Navigation

2009-2010 Undergraduate Calendar

Main Links
Related Links


Link to class schedule

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.

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

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