Skip to main content
CPE
551
Theory Of Computation
Reviews regular expressions and finite automata. studies turning machines and equivalent models of computation, the Chomsky hierarchy, context-free grammars, push-down automata, and computability. Machine models of effective computability; sub-recursive hierarchies; P and NP problems; effective and efficient reducibility; time, space, and abstract complexity.
Prerequisites:
0612-300, or Consent of the Instructor
0612551
(3-0-3)