CPSC 313: Introduction to Computability
General Course Information
Computer Science 313 is a second-year undergraduate course in the theory of computation offered by the Department of Computer Science at the University of Calgary. Until recently, it was a required course for computer science majors.
These pages — which are certainly “under construction” at this point — describe the course as it will be offered in Winter, 2022.
Course Outline
The course outline has now been approved (and the words “course outline” at the beginning of this sentence form a link to it).
Lectures and Tutorials
- Introduction to Course and Mathematics Review
- Finite Automata and Regular Expressions
- Context-Free Grammars
- Turing Machines
- Undecidability
- Conclusion
Other Course Information
A Resource That Some Students Find To Be Useful
JFLAP is a simple application that can be used to work with the simple machines that are studied at the beginning of this course. It is freely available. The software, information about how to use it, can be found at the JFLAP home page. Please note, though, that the JFLAP documentation should not be consulted for descriptions of things like “deterministic finite automata” that are introduced in this course, because these things are not always defined in exactly the same way.
