Fall 2021

- Official lecture times: Tuesday and Thursday, 16:05 - 17:25am.
- There won't be live lectures. Instead, links to pre-recorded video lectures are posted in the section "What was done in class".

- First lecture is on Thursday September 9.
- October 25-29: Fall break, no classes.
- Last lecture is on Thursday December 9.

- Office hours will start on Monday September 13 and will be online.
- Michiel Smid: Monday and Wednesday 10-11am, on Google Meet, click on the name.
- Marc Vicuna: Tuesday and Thursday 10-11am, on Zoom, click on the name. Meeting ID: 983 8610 1683, passcode: theory

- Assignment 1: posted September 23, due October 7
- Assignment 2: posted October 7, due October 21
- Midterm: Thursday November 4, online, during the official lecture time
- Assignment 3: posted November 11, due November 26
- Assignment 4: posted November 25, due December 9
- Final exam: Wednesday December 22, 9-11am, online

- Assignments: 25%
- Midterm: 25%
- Final exam: 50%

- 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 Thursday October 7, before 23:59.
- Assignment 2 is due Thursday October 21, before 23:59.
- Assignment 3 is due Friday November 26, before 23:59.
- Assignment 4 is due Thursday December 9, before 23:59.

- The midterm will be on Thursday November 4, between 3:50pm and 5:40pm.
- Sign in to Brightspace on Thursday November 4 by 3:50 and click the Midterm link to begin. If you have trouble finding the link, go to Tools-->Quizzes. 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 an old midterm so that
you get an idea of what to expect.
- Here are the answers.

- The final exam will be on Wednesday December 22, between 8:50 and 11:10am.
- Sign in to Brightspace on Wednesday December 22 by 8:50 and click the Final Exam link to begin. If you have trouble finding the link, go to Tools-->Quizzes. Once you start, you have 120 minutes.
- The final exam will be multiple choice. There will be 25 questions about every topic that we covered in class and in the assignments.
- Here is an old exam . Note that
this was a 3-hour exam.
- Here are the answers.

- 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.

- September 9:
- Video lecture 1, part 1: short introduction.
- Ignore the following video, because it is from winter 2021: Video lecture 1, part 1: short introduction.
- Video lecture 1, part 2.
- Overview; Sections 1.1 and 2.1; example on page 23. (Take a quick look at Sections 1.2 and 1.3.)

- September 14:
- Video lecture 2, part 1.
- Video lecture 2, part 2.
- Deterministic finite automata: definition and examples (Section 2.2).

- September 16:
- Union/intersection/complement of regular languages is regular; regular operations: union, concatenation, and star (Section 2.3);
- Video lecture 3.

- September 21:
- 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.

- September 23:
- Equivalence of deterministic and nondeterministic finite automata (Section 2.5).
- Video lecture 5.

- September 28:
- Closure under the regular operations (Section 2.6); Exercise 2.18.
- Video lecture 6.

- September 30:
- Regular expressions (Section 2.7); how to convert a regular expression to an NFA (Section 2.8.1).
- Video lecture 7.

- October 5:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video lecture 8.

- October 7:
- Pumping Lemma for regular languages (Section 2.9).
- Video lecture 9.

- October 12:
- Pumping Lemma, more examples (Section 2.9); introduction to context-free grammars (Section 3.1).
- Video lecture 10.

- October 14:
- Context-free grammars (Section 3.1); examples of context-free grammars (Section 3.2).
- Video lecture 11.

- October 19:
- 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.

- October 21:
- Deterministic pushdown automata; properly nested parentheses (Sections 3.5, 3.6.1).
- Video lecture 13.

- October 25-29: Fall break, no classes:
- November 2:
- Deterministic pushdown automata (Section 3.6.2); nondeterministic pushdown automata (Section 3.6.3).
- Video lecture 14.

- November 4: Midterm.
- November 9:
- 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 11:
- 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.

- November 16:
- 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.

- November 18:
- 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).
- Video lecture 18.

- November 23:
- 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 25:
- The Halting Problem is undecidable (Section 5.1.5); Hilbert's Hotel: countable sets, the real numbers are not countable (Section 5.2).
- Video lecture 20.

- November 30:
- The Halting Problem revisited (Section 5.2.1); Rice's Theorem (Section 5.3).
- Video lecture 21.

- December 2:
- Enumerable languages (Sections 5.4 and 5.5).
- Video lecture 22.

- December 7:
- 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 9:
- Review: Chapter 7.
- Video lecture 24.

- We are done!