Introduction to Theory of Computation (COMP 3803)
Fall 2022
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel(@scs.carleton.ca)
Lectures:
- Monday and Wednesday, 10:05 - 11:25, Tory Building 447.
- All lectures 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 is on Wednesday September 7.
- Monday October 10: holiday.
- October 24-28: Fall break, no classes.
- Last lecture is on Wednesday December 7.
Office hours:
- Office hours will start in the week of September 12 and will be
in-person only.
- Michiel Smid: Tuesday, 9-11am, Herzberg 5125C.
- Alma Arevalo Loyola: Thursday, 1-3pm, Herzberg 5174.
Course objectives:
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).
Textbook:
Important dates:
- Assignment 1: posted September 21, due October 5.
- Assignment 2: posted October 5, due October 19.
- Midterm: Wednesday November 2, in class (and in-person only).
- Assignment 3: posted November 9, due November 23.
- Assignment 4: posted November 23, due December 7.
- Final exam: Monday December 19, 9-11 am, Alumni Hall, in-person only.
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 Wednesday October 5, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here and
here are the figures.
- Here are the solutions
for Assignment 1.
- Assignment 2 is due Wednesday October 19, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here is the figure.
- Here are the solutions
for Assignment 2.
- Assignment 3 is due Wednesday November 23, before 23:59.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions
for Assignment 3.
- Assignment 4 is due Wednesday December 7, before 23:59.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
Assignments from the fall term of 2021:
Midterm:
- The midterm will be on Wednesday November 2, 10:00 - 11:25,
in-person, in Tory Building 447 (our regular classroom).
- 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 an old midterm so
that you get an idea of what to expect.
- Here is the midterm
without the answers.
- Here is the midterm
with the answers.
Final exam:
- The final exam will be in-person only. Details TBA.
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.
- 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
reduction.
- 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.
Note: While these are the standard penalties, more severe penalties may
be applied when warranted. For more information, click
here.
What was done in class (all links to video lectures are from previous
terms):
- September 7:
- September 12:
- September 14:
- Union/intersection/complement of regular languages is regular;
regular operations: union, concatenation, and star (Section 2.3).
- Introduction to nondeterministic finite automata (Sections 2.4.1
and 2.4.2).
- Video
lecture 3.
- September 19:
- Introduction to nondeterministic finite automata (Section 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 21:
- 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 26:
- Regular expressions (Section 2.7).
- How to convert a regular expression to an NFA (Section 2.8.1).
- Video
lecture 7.
- September 28:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video
lecture 8.
- October 3:
- October 5:
- Pumping Lemma, more examples (Section 2.9); introduction to
context-free grammars (Section 3.1).
- Video
lecture 10.
- October 10: Holiday
- October 12:
- Context-free grammars (Section 3.1); examples of context-free
grammars (Section 3.2).
- Video
lecture 11.
- October 17:
- 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, few details how to convert CFG to CNF).
- Video
lecture 12.
- October 19:
- Deterministic pushdown automata; a^n b^n (Sections 3.5, 3.6.2).
- Video
lecture 13.
- October 24-28: Fall break.
- October 31:
- Deterministic pushdown automata; properly nested parentheses
(Sections 3.5, 3.6.1).
- Nondeterministic pushdown automata (Section 3.6.3).
- Video
lecture 14.
- November 2: Midterm.
- November 7:
- 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 9:
- Proof of the pumping lemma (Section 3.8.1); second example in
Section 3.8.2.
- Video
lecture 16.
- November 14:
- 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 16:
- 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 21:
- 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 23:
- November 28:
- The Halting Problem revisited (Section 5.2.1); Rice's Theorem
(Section 5.3).
- Video
lecture 21.
- November 30:
- December 5:
- 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.
Tentative schedule, based on the last time I taught this course.