CSC 3312 - Theory of Computation

Credits: 4
This course studies the abstract models of machines and languages recognized by them, and introduces the concept of computability. This course not only serves as the theoretical foundation of computer science, but also has wide application to programming languages linguistics, natural language processing, compiler design, and software design. Topics include finite automata and regular languages, pushdown automata and context-free grammars, grammar transformations and normal forms, Turing machines and computable functions, and unsolvable problems including the halting problem.

Prerequisites MAT-2224 or CSC-1109 or MAT-1109