CSC 4170: Theory of Computation
Finite automata and regular expressions; push down automata and context-free grammars; Turing machines; Church's thesis; computability; NP-completeness.
- 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.