Introduction to Theory of Computation (COMP 3803)
Fall 2025
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel@scs.carleton.ca
Course outline:
Lectures:
- Tuesday and Thursday, 2:35-3:55, check Carleton Central for the
classroom.
- Lectures, tests, and final exam will be in-person.
- You are strongly encouraged to come to class. In the section "What
was done in class", you will find links to video lectures from winter
2021. These videos can be useful if, for some reason, you miss
some classes.
Fall term:
- First lecture: Thursday September 4.
- October 20-24: Fall break, no classes.
- Last lecture: Thursday December 4.
Office hours:
- Office hours will start in the week of September 8 and will be
in-person only.
- Alma: Wednesday 1-2, Herzberg 4115
- Hussein: Tuesday 9:30-10:30, Herzberg 4115
- Michiel: Wednesday 9-10, Herzberg 5125C
Course calendar description:
Theoretical aspects of computer science. Topics include: formal
languages and automata theory, computability theory.
Prerequisite: COMP 2804.
Precludes additional credit for COMP 2805 (no longer offered).
Lectures three hours a week.
List of topics:
Formal languages and automata theory: regular languages, finite
automata, context-free languages, pushdown automata.
Computability theory: Turing machines, Church-Turing Thesis,
decidability, Halting Problem.
Textbook:
Important dates:
- Test 1, in class: Thursday October 9.
- Test 2, in class: Thursday October 30.
- Test 3, in class: Thursday November 20.
Grading scheme:
- Test 1: 16%
- Test 2: 17%
- Test 3: 17%
- Final exam: 50%
Problem sets:
- There will be five problem sets. You do not hand them in and they
will not be marked. They are meant to prepare you for the tests and
final exam. Solutions will be posted.
- Problem set 1: posted on September 11, solutions posted on
September 25.
- Here is problem set 1.
- Here are the solutions
for problem set 1.
- Problem set 2: posted on September 25, solutions posted on
October 2.
- Here is problem set 2.
- Here are the solutions
for problem set 2.
- Problem set 3: posted on October 8, solutions posted on
October 23.
- Here is problem set 3.
- Here are the solutions
for problem set 3.
- Problem set 4: posted on November 3, solutions posted on
November 13.
- Problem set 5: posted on November ??, solutions posted on
December 4.
Test 1:
- The first test will be on Thursday October 9, 2:30-3:55, in-person,
in our regular classroom.
- It will be a written test.
- You are supposed to know everything that was done in class up to,
and including, the algorithm for converting a DFA to a regular
expression, as well as problem sets 1 and 2.
- Here is Test 1 and
here are the solutions.
Test 2:
- The second test will be on Thursday October 30, 2:30-3:55, in-person,
in our regular classroom.
- It will be a multiple-choice test.
- You are supposed to know everything that was done in class, starting
from the pumping lemma and ending with the conversion of a DFA to a
context-free grammar, as well as problem set 3.
- Here is Test 2 and
here are the answers.
Assignments from the fall term of 2022:
What was done in class (all links to video lectures are from previous
terms):
- September 4:
- September 9:
- September 11:
- Union/intersection/complement of regular languages is regular;
regular operations: union, concatenation, and star (Section 2.3).
- Introduction to nondeterministic finite automata
(Section 2.4.1).
- Video
lecture 3.
- September 16:
- Introduction to nondeterministic finite automata
(Sections 2.4.2 and 2.4.3), definition of nondeterministic
finite automaton (Section 2.4.4).
- Converting an NFA without epsilon-transitions to a DFA
(Section 2.5).
- Video
lecture 4.
- September 18:
- September 23:
- Exercise 2.18.
- Regular expressions (Section 2.7).
- How to convert a regular expression to an NFA (Section 2.8.1).
- Video
lecture 7.
- September 25:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video
lecture 8.
- September 30:
- October 2:
- October 7:
- Context-free grammars (Section 3.1); examples of context-free
grammars (Section 3.2).
- Video
lecture 11.
- October 9:
- October 14:
- No lecture. Watch the video.
- Converting a DFA to a CFG; every regular language is context-free
(Section 3.3); Chomsky Normal Form (Section 3.4; definition of
CNF, sketch how to convert CFG to CNF).
- Video
lecture 12.
- October 16:
- No lecture. Watch the video.
- Deterministic pushdown automata; a^n b^n (Sections 3.5, 3.6.2).
- Video
lecture 13.
- October 20-24:
- October 28:
- Deterministic pushdown automata; properly nested parentheses
(Sections 3.5, 3.6.1).
- Nondeterministic pushdown automata (Section 3.6.3).
- Video
lecture 14.
- October 30:
Tentative schedule, based on the last time I taught this course.
Ignore the dates, they are from last year.
- October 18:
- Converting a context-free grammar to a nondeterministic pushdown
automaton (Section 3.7); statement of the pumping lemma for
context-free languages (Section 3.8); first example in
Section 3.8.2.
- Video
lecture 15.
- November 1:
- Statement of the pumping lemma (Section 3.8); examples in
Section 3.8.2.
- Video
lecture 16.
- November 6:
- Proof of the pumping lemma (Section 3.8.1).
-
Turing machines
(Section 4.1); accepting palindromes using a one-tape Turing
machine (Section 4.2.1).
- Video
lecture 17.
- November 8:
- Accepting palindromes using a two-tape Turing machine
(Section 4.2.2).
- More examples of Turing machines (Sections 4.2.3, 4.2.4, 4.2.5).
- Equivalence of multi-tape Turing machines and single-tape Turing
machines (Section 4.3).
- Video
lecture 18.
- November 13:
- What is an algorithm? Church-Turing Thesis (Section 4.4);
definition of a language being decidable (Section 5.1);
the languages A_DFA, A_NFA, and A_CFG are decidable; every
context-free language is decidable (Sections 5.1.1, 5.1.2,
5.1.3).
- The Halting
Problem is undecidable (Section 5.1.5).
- Video
lecture 19.
- November 15:
- November 20:
- November 22:
- November 27:
- Language A is decidable if and only if both A and its complement
are enumerable (Section 5.7); Halt is enumerable, but its
complement is not enumerable (Section 5.7); both EQ_TM and its
complement are not enumerable (Section 5.8); the set of all
enumerable languages is countable (Section 5.6.1); the set of
all languages is not countable (Section 5.6.2).
- Video
lecture 23.
- November 29: