Fall 2023

- Monday and Wednesday, 16:05-17:25, Southam Hall 520.
- 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.

- First lecture: Wednesday September 6.
- Monday October 9: holiday.
- October 23-27: Fall break, no classes.
- Last lecture: Wednesday December 6.
- No lecture on Friday December 8 (classes follow a Monday schedule).

- Office hours will start in the week of September 11 and will be in-person only.
- Michiel Smid: Monday, 9-10, Herzberg 5125C.
- Alma Arevalo Loyola: Monday, 10-11, Herzberg 5174.
- Alexander Nedev: Wednesday, 12:30pm-1:30pm, Herzberg 5174.

- Assignment 1: posted September 21, due October 5.
- Assignment 2: posted October 5, due October 19.
- Midterm: Wednesday November 1, in class (and in-person only).
- Assignment 3: posted November 9, due November 23.
- Assignment 4: posted November 23, due December 7.
- Final exam: Wednesday December 20, 9-11, in-person only.

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

- The midterm will be on Wednesday November 1, 16:00-17:25, in-person, in Southam Hall 520 (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 are the answers.

- The final exam will be on Wednesday December 20, 9-11, in-person. Location TBA.
- The final exam will be multiple choice. There will be 25 questions. You are supposed to know everything that was done in class and the four assignments.
- Here is an old exam.
- Here are the answers.

- If you are unsure of the expectations regarding academic integrity (how to use and cite references, if unauthorized collaboration with lab- or classmates is permitted (and, if so, to what degree), then you must ask your instructor. Sharing assignment or quiz specifications or posting them online (to sites like Chegg, CourseHero, OneClass, etc.) is ALWAYS considered academic misconduct. You are NEVER permitted to post, share, or upload course materials without explicit permission from your instructor. Academic integrity offences are reported to the office of the Dean of Science. Information, process and penalties for such offences can be found on the ODS webpage.
- Many of the assessed activities in this course were designed to be completed by an individual working alone. Unless it is explicitly stated otherwise, the use of any will be considered academic misconduct. This includes, but is not limited to, chatbots (e.g., ChatGPT, Google Bard, Bing Chart), research assistants (e.g., Elicit), and image generators (e.g., Stable Diffusion, Dall-E), etc.

- September 6:
- Overview; Sections 1.1 and 2.1; example on page 23. (Take a quick look at Sections 1.2 and 1.3.)
- Video from fall 2021; note that dates refer to fall 2021: Video lecture 1, part 1: short introduction.
- Video from winter 2021; note that dates refer to winter 2021: Video lecture 1, part 1: short introduction.
- Video lecture 1, part 2.

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

- September 13:
- 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 18:
- 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.

- 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:
- Pumping Lemma for regular languages (Section 2.9).
- Video lecture 9.

- 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:
- 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 27:
- The Halting Problem revisited (Section 5.2.1); Rice's Theorem (Section 5.3).
- Video lecture 21.

- November 29:
- Enumerable languages (Sections 5.4 and 5.5).
- Video lecture 22.

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

- December 8:
- No lecture.