Winter 2019

- TA's office hours will be held in Herzberg Building 5356
- Darryl Hill

Office hours: Thursday 1-3 - Yunkai Wang

Office hours: Tuesday 1-3

- Assignment 1: posted January 17, due January 31
- Assignment 2: posted January 31, due February 15
- Midterm: Thursday February 28
- Assignment 3: posted March 7, due March 21
- Assignment 4: posted March 21, due April 4
- Final exam: Thursday April 18, 7-9pm

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

- 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).
- Instructions on how to submit your assignment can be found here.

- Assignment 1 is due Thursday January 31, before 11:55pm.
- Assignment 2 is due Thursday February 15, before 11:55pm.
- Assignment 3 is due Thursday March 21, before 11:55pm.
- Assignment 4 is due Thursday April 4, before 11:55pm.

- The midterm will be on Thursday February 28, in class. It will be a multiple-choice exam. 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 in 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.
This term's midterm will have a few more questions.
- Here are the answers.

- Here is the midterm from this term.

Answers: 1D, 2C, 3B, 4B, 5C, 6C, 7A, 8D, 9A, 10B, 11B, 12A, 13D, 14C, 15A, 16B, 17D, 18C

- 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 the final exam from the
last time I taught this course.
- Here are the answers.

- January 8: Overview; Sections 1.1 and 2.1; example on page 23. (Take a quick look at Sections 1.2 and 1.3.)
- January 10: Deterministic finite automata: definition and examples (Section 2.2).
- January 15: Union of two regular languages is regular, regular operations: union, concatenation, and star (Section 2.3); introduction to NFAs (Section 2.4.1).
- January 17: Nondeterministic finite automata (Sections 2.4.1, 2.4.2, and 2.4.3), definition of nondeterministic finite automaton (Section 2.4.4); equivalence of deterministic and nondeterministic finite automata without epsilon-transitions (Section 2.5).
- January 22: Equivalence of deterministic and nondeterministic finite automata (Section 2.5); closure under the regular operations (Section 2.6).
- January 24: Exercise 2.18, regular expressions (Section 2.7); how to convert a regular expression to an NFA (Section 2.8.1).
- January 29: How to convert a DFA to a regular expression (Section 2.8.2).
- January 31: 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: Midterm, in class.
- 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: Countable sets, the real numbers are not countable (Section 5.2); the Halting Problem is undecidable (Section 5.2.1); the language A_TM is undecidable (Section 5.1.4); 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. Read Chapter 7.