Course Information

CSC 4170: Theory of Computation

Credits: 3 Level: undergraduate


Finite automata and regular expressions; push down automata and context-free grammars; Turing machines; Church's thesis; computability; NP-completeness.

Course Outcomes:
  • Demonstrate an understanding of the Chomsky hierarchy of grammars and languages.

  • Demonstrate understanding of fundamental concepts of theoretical computer science, such as decidability, undecidability, recognizability, etc.

  • Demonstrate an understanding of basic complexity theory and NP-completeness.

  • Develop skills in generating mathematically rigorous definitions and proofs.


CSC 1700