Fall 2024

- Click here.

- Wednesday and Friday, 11:35-12:55, check Carleton Central for the classroom.
- 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 4.
- October 21-25: Fall break, no classes.
- Last lecture: Wednesday December 4.
- No lecture on Friday December 6 (classes follow a Monday schedule).

- Office hours will start in the week of September 9 and will be in-person only.
- Michiel Smid: Tuesday, 10-11, Herzberg 5125C.
- Alma Arevalo Loyola: Monday, 11-noon, Herzberg 4115.
- Ajay Sandhu: Tuesday 1-2, Herzberg 4115.

- Assignment 1: posted September 13, due September 27.
- Assignment 2: posted October 4, due October 18.
- Midterm: October 30, in class (and in-person only).
- Assignment 3: posted November 1, due November 15.
- Assignment 4: posted November 15, due November 29.
- Final exam: TBA.

- 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 Friday September 27, before 23:59.

- Information will be posted here.

- Information will be posted here.

- September 4:
- 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 6:
- Deterministic finite automata: definition and examples (Section 2.2).
- Video lecture 2, part 1.
- Video lecture 2, part 2.

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