Introduction to Theory of Computation (COMP 3803)
Office: Herzberg Building 5125C (But: we are not allowed to
- Official lecture times: Monday and Wednesday, 10:05 - 11:25am.
- There won't be live lectures. Instead, links to pre-recorded video
lectures will be posted in the section "What was done in class".
- First lecture is on Monday January 11.
- February 15-19: Winter break, no classes.
- Last lecture is on Monday April 12.
- Wednesday April 14: Last day of classes in the winter term. Classes
follow a Friday schedule.
Mohammad Nokhbeh Zaeem: Monday, 2-4pm, on Zoom, click on the name.
- Michiel Smid:
Tuesday and Thursday, 4-5pm, on Google Meet, click on the name.
- Yunkai Wang: Wednesday, 2-4pm, on Discord, username: Yunkai#3311
Theoretical aspects of computer science.
Topics covered include:
Formal languages and automata theory (regular languages, finite
automata, context-free languages, pushdown automata),
computability theory (Turing machines, Church-Turing Thesis,
decidability, Halting Problem).
- Assignment 1: posted January 24, due February 7
- Assignment 2: posted February 7, due February 28
- Midterm: Monday March 1, 10:00 - 11:30am
- Assignment 3: posted March 14, due March 28
- Assignment 4: posted March 28, due April 11
- Final exam: Saturday April 24, 9-11am
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
- Late assignments will not be accepted.
- Real computer scientists use
LaTeX to type
their solutions. In case you want to learn LaTeX,
here is a tutorial.
- You can use the freely available
drawing editor to make figures.
- Each assignment must be submitted as one single PDF file through
- You can type your solutions, or write them by hand and scan them
(for example, using a scan app on your phone or using a real
- Assignment 1 is due Sunday February 7, before 23:59.
- Here is Assignment 1 as a
- Here is the LaTeX file.
- Here and
here are the figures.
- Here are the solutions.
- Assignment 2 is due Sunday February 28, before 23:59.
- Here is Assignment 2 as a
- Here is the LaTeX file.
- Here is the figure.
- Here are the solutions.
- The midterm will be on Monday March 1, between 9:50 and 11:40am.
- Sign in to cuLearn on Monday March 1 by 9:50 and click the midterm
link in Topic 3 to begin. Once you start, you have 90 minutes.
- It will be a multiple-choice exam with 18 questions. There will only
be questions about regular languages. Thus, you are supposed to know
everything that was done in class up to, and including, the pumping
lemma, as well as the first two assignments.
- Here is the midterm from the
last time I taught this course. This was my first-ever
multiple-choice exam, and it is the only one I have for this course.
- Saturday April 24, 9-11am.
Academic Integrity (New, Please Read):
As of 2020, there are new penalties in place for academic integrity
violations. These will be issued by the Associate Dean (Undergraduate
Affairs) of Science to students who copy, in whole or in part, work
they submit for assignments.
Note: While these are the standard penalties, more severe penalties may
be applied when warranted. For more information, click
- First offence, first-year students (less than 4.0 credits completed):
No credit for assessment(s) in question, or a final grade reduction of
one full letter grade (e.g., A- becomes B-), whichever is a greater
- First offence (anyone else): A grade of F in the course.
- Second offence (anyone): A grade of F in the course and a one-term
suspension from studies.
- Third offence: Expulsion from the University.
What was done in class:
- January 11:
- January 13:
- January 18:
- Union/intersection/complement of regular languages is regular;
regular operations: union, concatenation, and star (Section 2.3);
- January 20:
- Nondeterministic finite automata (Sections 2.4.1, 2.4.2, and
2.4.3), definition of nondeterministic finite automaton
- January 25:
- Equivalence of deterministic and nondeterministic finite
automata (Section 2.5).
- January 27:
- Closure under the regular operations (Section 2.6);
- February 1:
- Regular expressions (Section 2.7); how to convert a regular
expression to an NFA (Section 2.8.1).
- February 3:
- How to convert a DFA to a regular expression (Section 2.8.2).
- February 8:
- February 10:
- Pumping Lemma, more examples (Section 2.9); introduction to
context-free grammars (Section 3.1).
- February 15-19: Winter break.
- February 22:
- Context-free grammars (Section 3.1); examples of context-free
grammars (Section 3.2).
- February 24:
- More examples of context-free grammars (Section 3.2); converting
a DFA to a CFG, every regular language is context-free
(Section 3.3); Chomsky Normal Form (Section 3.4; definition of
CNF only, no details).
- March 1:
- Midterm, 10:00 - 11:30am.
- March 3:
- Deterministic pushdown automata; properly nested parentheses
(Sections 3.5, 3.6.1).
- March 8:
- Deterministic pushdown automata (Section 3.6.2);
nondeterministic pushdown automata (Section 3.6.3).
- March 10:
- 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
- March 15:
- Proof of the pumping lemma (Section 3.8.1); example of a
language that is not context-free (Section 3.8.2).
- March 17:
- One more example of a language that is not context-free
(Section 4.1); accepting palindromes using a one-tape Turing
machine (Section 4.2.1).
- March 22:
- Accepting palindromes using a two-tape Turing machine
- More examples of Turing machines (Sections 4.2.3, 4.2.5);
equivalence of multi-tape Turing machines and single-tape Turing
machines (Section 4.3).
- Lecture 18.
Tentative schedule, based on the last time I taught this course.
Ignore the dates below, they are from last time.
- March 21: 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).
- March 26:
countable sets, the real numbers are not countable (Section 5.2);
the Halting Problem revisited (Section 5.2.1);
introduction to Rice's Theorem (Section 5.3).
- March 28: Rice's Theorem (Section 5.3).
- April 2: Enumerable languages (Sections 5.4 and 5.5).
- April 4: 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).
- April 9: Review: Chapter 7.