Course Description
An introduction to the theoretical foundations of computer science, examining finite automata, context-free grammars, Turing machines, decidability and undecidability, and complexity theory. Strategies will be developed to help categorize problems as tractable or intractable.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 1:30pm–2:20pm; Wednesday, 12:30pm–1:20pm; Friday, 11:30am–12:20pm
All lectures are held in the Annex, room 23A.
Textbook
Required text: T. J. Smith, Theory of Computing: An Open Introduction. Self-published open educational resource, α pre-publication edition, 2024.
Recommended text: M. Sipser, Introduction to the Theory of Computation. Cengage, 3rd edition, 2012.
The required course textbook includes all material that will be discussed in each lecture. The recommended course textbook can be used as an optional supplement.
Marking Scheme
- Four assignments (12.5% each, total 50%)
- Midterm examination (25%)
- Final examination (25%)
You must write the final examination in order to pass the course, even if the weighted sum of your assignment and midterm examination grades is at least 50%.
News
- Dec. 8: The final exam will be written on Dec. 15. See the review document and the Exams section below for details. A practice final exam is also available.
- Dec. 5: Due to the delayed opening of the university today, the lecture this morning is cancelled.
- Nov. 21: The fourth assignment has been posted. It is due by Dec. 5 at 11:30am.
- Oct. 24: The third assignment has been posted. It is due by Nov. 7 at 11:30am.
- Oct. 17: The midterm will be written next week during the Oct. 24 lecture. See the review document and the Exams section below for details. A practice midterm is also available.
- Oct. 15: The lecture on Friday will be cancelled due to the instructor being away.
- Sep. 26: The second assignment has been posted. It is due by Oct. 10 at 11:30am.
- Sep. 24: As mentioned in lecture today, the lectures on Friday and next Monday will be cancelled due to the instructor being away.
- Sep. 5: The first assignment has been posted. It is due by Sep. 19 at 11:30am.
- Sep. 3: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Notes | Readings |
| 1 | Introduction, regular expressions | TOCOpen, 1.1 |
| 2 | Finite automata, nondeterminism | TOCOpen, 1.2 |
| 3 | Conversions between regular models | TOCOpen, 1.3 |
| 4 | Closure properties of regular languages, proving nonregularity | TOCOpen, 1.4–1.5 |
| 5 | Context-free grammars, ambiguity | TOCOpen, 2.1 |
| 6 | Normal forms, pushdown automata | TOCOpen, 2.1–2.2 |
| 7 | Conversions between CF models; Mid-course review, midterm examination | TOCOpen, 2.3 |
| 8 | Closure properties of CF languages, proving non-CFness | TOCOpen, 2.4–2.5 |
| 9 | Turing machines and variants | TOCOpen, 3.1–3.2 |
| – | Fall study break | – |
| 10 | Universal Turing machines, Church–Turing thesis | TOCOpen, 3.5–3.6 |
| 11 | Decidability and undecidability | TOCOpen, 4.1–4.4 |
| 12 | Reducibility | TOCOpen, 5.1–5.3 |
Assignments
- Assignment 1, due Sep. 19
- Assignment 2, due Oct. 10
- Assignment 3, due Nov. 7
- Assignment 4, due Dec. 5
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
Exams
Midterm
Date: Oct. 24, 2025
Time: 11:30am–12:20pm
Place: Annex, Room 23A
Content: All material from Weeks 1 to 6
Final Exam
Date: Dec. 15, 2025
Time: 2:00pm–4:30pm
Place: Annex, Room 23A
Content: Primarily material from Weeks 7 to 12, some earlier material
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday 11:30am–12:20pm/Wednesday 10:30am–11:20am/Friday 9:30am–10:20am, or by appointment