Introduction to Theory of Computation (COMP 3803)
Fall 2024
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel@scs.carleton.ca
Plagiarism, integrity, university policies:
Lectures:
- Wednesday and Friday, 11:35-12:55, check Carleton Central for the
classroom.
- Lectures, midterm, and final exam will be in-person.
- In the section "What was done in class", you will find links to
video lectures from winter 2021.
Fall term:
- First lecture: Wednesday September 4.
- October 21-25: Fall break, no classes.
- Last lecture: Wednesday December 4.
- No lecture on Friday December 6 (classes follow a Monday schedule).
Office hours:
- Office hours will start in the week of September 9 and will be
in-person only.
- Michiel Smid: Tuesday, 10-11, Herzberg 5125C.
- Alma Arevalo Loyola: Monday, 11-noon, Herzberg 4115.
- Ajay Sandhu: Tuesday 1-2, Herzberg 4115.
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:
- Assignment 1: posted September 13, due September 27.
- Assignment 2: posted October 4, due October 18.
- Midterm: October 30, in class (and in-person only).
- Assignment 3: posted November 1, due November 15.
- Assignment 4: posted November 15, due November 29.
- Final exam: TBA.
Grading scheme:
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
Assignments:
- Late assignments will not be accepted.
- You are encouraged to use
LaTeX to type
your solutions. In case you want to learn LaTeX,
here is a tutorial.
- You can use the freely available
Ipe
drawing editor to make figures.
- Each assignment must be submitted as one single PDF file through
Brightspace.
- 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
scanner).
- Assignment 1 is due Friday September 27, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here and
here are the figures.
Assignments from the fall term of 2022:
Midterm:
- Information will be posted here.
Final exam:
- Information will be posted here.
What was done in class (all links to video lectures are from previous
terms):
- September 4:
- September 6:
- 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 13:
- 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.
Tentative schedule, based on the last time I taught this course.
IGNORE ALL DATES BELOW; THEY ARE FROM LAST YEAR!!!!!!!!!!!
- September 20:
- Converting an arbitrary NFA to a DFA (Section 2.5).
- Closure under the regular operations (Section 2.6);
Exercise 2.18.
- Video
lecture 5.
- Video
lecture 6.
- September 25:
- Regular expressions (Section 2.7).
- How to convert a regular expression to an NFA (Section 2.8.1).
- Video
lecture 7.
- September 27:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video
lecture 8.
- October 2:
- October 4:
- Pumping Lemma, more examples (Section 2.9); introduction to
context-free grammars (Section 3.1).
- Video
lecture 10.
- October 9: Holiday
- October 11:
- Context-free grammars (Section 3.1); examples of context-free
grammars (Section 3.2).
- Video
lecture 11.
- October 16:
- 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 18:
- Deterministic pushdown automata; a^n b^n (Sections 3.5, 3.6.2).
- Video
lecture 13.
- October 23-27: Fall break.
- October 30:
- Deterministic pushdown automata; properly nested parentheses
(Sections 3.5, 3.6.1).
- Nondeterministic pushdown automata (Section 3.6.3).
- Video
lecture 14.
- November 1: Midterm.
- November 6:
- 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 8:
- Proof of the pumping lemma (Section 3.8.1); second example in
Section 3.8.2.
- Video
lecture 16.
- November 13:
- Pumping Lemma: third example in Section 3.8.2.
-
Turing machines
(Section 4.1); accepting palindromes using a one-tape Turing
machine (Section 4.2.1).
- Video
lecture 17.
- November 15:
- 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).
- Video
lecture 18.
- November 20:
- Equivalence of multi-tape Turing machines and single-tape Turing
machines (Section 4.3).
- 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).
- Video
lecture 19.
- November 22:
- November 27:
- The Halting Problem revisited (Section 5.2.1); Rice's Theorem
(Section 5.3).
- Video
lecture 21.
- November 29:
- December 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).
- Video
lecture 23.
- December 6: