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 14
- Midterm: Thursday February 28
- Assignment 3: posted March 7, due March 21
- Assignment 4: posted March 21, due April 4
- Final exam: TBA

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

- Information about the midterm will be posted here.

- Information about the final exam will be posted here.

- 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); Exercise 2.18.
- January 24: 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).
- February 5: Proof of the Pumping Lemma for regular languages (Section 2.9); definition of context-free grammars (Section 3.1); properly nested parentheses (Section 3.2.1).
- February 7: Examples of context-free grammars (Section 3.2); converting a DFA to a CFG, every regular language is context-free (Section 3.3).
- February 12: 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; the intersection of two context-free languages may not be context-free; the intersection of a context-free language and a regular language is context-free.
- March 14: Turing machines (Section 4.1); examples of Turing machines (Sections 4.2.1 and 4.2.2).
- March 19: Example of a Turing machine (Section 4.2.5); equivalence of multi-tape Turing machines and single-tape Turing machines (Section 4.3). What is an algorithm? Church-Turing Thesis (Section 4.4).
- March 21: 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 (Sections 5.1.5 and 5.2.1).
- March 26: Countable sets, the real numbers are not countable (Section 5.2); 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.