Semester Offered: Second Semester Credits (Range): 3 hours Attribute:3NS, QP-F This course examines three increasingly powerful mathematical models of computation. For each model, we explore its capabilities, limitations and variants. Emphasis is placed on abstraction and formal mathematical reasoning. Topics include finite automata and regular expressions, non-determinism, context-free grammars and pushdown automata, Turing machines, undecidability, recursive and recursively enumerable sets, and complexity classes.
Instructor: T. Wexler Prerequisites & Notes Pre-requisites: CSCI 280 and Math 220.