CSC 4170
Theory of Computation
3 Credits Format: lecture Level: undergraduate
Description: Finite automata and regular expressions; push down automata and context-free grammars; Turing machines; Church's thesis; computability; NP-completeness.
Textbooks:
- Introduction to the Theory of Computation, 2nd Edition, Sipser, Course Technology
Objectives:
- Establish an understanding of the Chomsky hierarchy of grammars and languages.
- Establish an understanding of the mathematical models of machines that act as acceptors for each of the principal classes of grammars and languages, including finite automata, push-down automata, and Turing machines.
- Establish an understanding of computability and NP-completeness.
- Establish an understanding of formal proofs that address language structure.
Coordinator: Dr. William Fleischman
Prerequisites: CSC 1700
Required For:
- Computer Science Major
Elective For:
- Computer Science Minor
- Cognitive Science Concentration
- Cognitive Science Minor
- Mathematics Minor