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: TBA
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.
Midterm:
- The midterm will be on Monday March 1, 10:00 - 11:30am.
- Details TBA.
Final exam:
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.
Tentative schedule, based on the last time I taught this course.
Ignore the dates below, they are from last time.
- January 31: How to convert a DFA to a regular expression
(Section 2.8.2). The Pumping Lemma for regular languages
(Section 2.9); some examples from Section 2.9.1.
- February 5: Pumping Lemma: more examples from Section 2.9.1;
brief introduction to context-free grammars (Section 3.1).
- February 7: Definition of context-free grammars (Section 3.1);
examples of context-free grammars (Section 3.2).
- February 12: Converting a DFA to a CFG, every regular language is
context-free (Section 3.3); Chomsky Normal Form; converting a
context-free grammar to Chomsky Normal Form (Section 3.4).
- February 14: Deterministic pushdown automata (Sections 3.5, 3.6.1,
3.6.2).
- February 18-22: Winter break.
- February 26: Nondeterministic pushdown automata (Section 3.6.3);
converting a context-free grammar to a nondeterministic pushdown
automaton (Section 3.7).
- February 28: ???
- March 5: Pumping lemma for context-free languages (Section 3.8);
proof of the pumping lemma (Section 3.8.1); first example in
Section 3.8.2.
- March 7: Examples of languages that are not context-free
(Section 3.8.2).
- March 12: Solutions midterm.
- March 14:
Turing
machines (Section 4.1);
examples of Turing machines (Sections 4.2.1 and 4.2.2).
- March 19: 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).
- 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.