Introduction to Theory of Computation (COMP 3803)
Winter 2021
Instructor:
Michiel Smid
Office: Herzberg Building 5125C (But: we are not allowed to
enter Herzberg.)
E-mail: michiel(@scs.carleton.ca)
Lectures:
- 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".
Winter term:
- 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.
Office hours:
-
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
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 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
Grading scheme:
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
Assignments:
- 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
Ipe
drawing editor to make figures.
- Each assignment must be submitted as one single PDF file through
cuLearn.
- 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 Sunday February 7, 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.
- Assignment 2 is due Sunday February 28, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here is the figure.
- Here are the solutions.
Midterm:
- 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.
Final exam:
- 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.
- 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:
- January 11:
- January 13:
- January 18:
- Union/intersection/complement of regular languages is regular;
regular operations: union, concatenation, and star (Section 2.3);
- Video
lecture 3.
- January 20:
- Nondeterministic finite automata (Sections 2.4.1, 2.4.2, and
2.4.3), definition of nondeterministic finite automaton
(Section 2.4.4).
- Video
lecture 4.
- January 25:
- Equivalence of deterministic and nondeterministic finite
automata (Section 2.5).
- Video
lecture 5.
- January 27:
- Closure under the regular operations (Section 2.6);
Exercise 2.18.
- Video
lecture 6.
- February 1:
- Regular expressions (Section 2.7); how to convert a regular
expression to an NFA (Section 2.8.1).
- Video
lecture 7.
- February 3:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video
lecture 8.
- February 8:
- February 10:
- Pumping Lemma, more examples (Section 2.9); introduction to
context-free grammars (Section 3.1).
- Video
lecture 10.
- February 15-19: Winter break.
- February 22:
- Context-free grammars (Section 3.1); examples of context-free
grammars (Section 3.2).
- Video
lecture 11.
- 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).
- Video
lecture 12.
- March 1:
- Midterm, 10:00 - 11:30am.
- March 3:
- Deterministic pushdown automata; properly nested parentheses
(Sections 3.5, 3.6.1).
- Video
lecture 13.
- March 8:
- Deterministic pushdown automata (Section 3.6.2);
nondeterministic pushdown automata (Section 3.6.3).
- Video
lecture 14.
- 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
Section 3.8.2.
- Video
lecture 15.
- March 15:
- Proof of the pumping lemma (Section 3.8.1); example of a
language that is not context-free (Section 3.8.2).
- Video
lecture 16.
- March 17:
- One more example of a language that is not context-free
(Section 3.8.2).
-
Turing machines
(Section 4.1); accepting palindromes using a one-tape Turing
machine (Section 4.2.1).
- Video
lecture 17.
- March 22:
- Accepting palindromes using a two-tape Turing machine
(Section 4.2.2).
- 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:
Hilbert's Hotel:
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.