CSCI 356: Theory of Computing (Fall 2023)

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 J. Bruce Brown Hall, room 236.

Special Note for Fall 2023. On Tuesday, December 5, the Monday schedule of classes and labs will be offered again. On Wednesday, December 6, the Friday schedule of classes and labs will be offered.


M. Sipser, Introduction to the Theory of Computation. Cengage, 3rd edition, 2012.

The textbook is available for sale at the campus bookstore. Course notes will also be provided for each lecture.

Marking Scheme

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%.



Week Notes Readings
1 Introduction, mathematical preliminaries Sipser, 0.1–0.2
2 Regular languages: regular expressions, finite automata Sipser, 1.1, 1.3
3 Regular languages (cont’d): nondeterminism, closure properties Sipser, 1.2
4 Regular languages (cont’d): conversions Sipser, 1.2–1.3
5 Regular languages (cont’d): proving nonregularity; Context-free languages: grammars Sipser, 1.4, 2.1
6 Context-free languages (cont’d): ambiguity, Chomsky normal form Sipser, 2.1
7 Context-free languages (cont’d): PDAs; mid-course review, midterm examination Sipser, 2.2
8 Context-free languages (cont’d): conversion between CFGs and PDAs Sipser, 2.2
9 Context-free languages (cont’d): proving non-context-freeness; Beyond context-free: Turing machines Sipser, 2.3, 3.1
Fall study break
10 Beyond context-free (cont’d): variants of TMs, universal TMs Sipser, 3.2
11 Beyond context-free (cont’d): Church-Turing thesis; Decidability Sipser, 3.3, 4.1
12 Undecidability; Reducibility Sipser, 4.2, 5.1
12.5 Reducibility (cont’d) Sipser, 5.3


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.



Date: Oct. 18, 2023
Time: 12:30pm–1:20pm
Place: J. Bruce Brown Hall, Room 236
Content: All material from Weeks 1 to 6

Final Exam

Date: Dec. 11, 2023
Time: 2:00pm–4:30pm
Place: Mulroney Hall, Room 3022
Content: Primarily material from Weeks 7 to 12, some earlier material



Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday/Wednesday/Friday, 9:30am–10:30am