CSCI3130: Formal Languages and Automata Theory — Fall 2018
This is the webpage for a previous offering of the course in 2018; latest offering available here
Siu On CHAN Office hours Tuesday 2:30-4:30pm SHB 911
Teaching assistants
- Hiu Sze Grace CHAM hscham@cse Thu 10:30-11:30 SHB 905
- Jingjing Jessica LI lijj@cse Tue 9-10 SHB 1024
- Sing Hei Ray LI shli@cse Thu 1:30-2:30 SHB 117
- Zhizhen Euclid YE zzye@cse Fri 2:30-3:30 SHB 117
News
- Dec 18: Homework 6 solution has been posted on Piazza (under Resources)
- Dec 11: Homework 5 solution has been posted on Piazza (under Resources)
- Nov 28: Week 13 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 28: Homework 6 is now posted
- Nov 26: The final exam will allow a single-sided (only 1 page, not both pages), handwritten A4 or lettersize cheatsheet
- Nov 23: Homework 3 solution has been posted on Piazza (under Resources)
- Nov 23: Week 12 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 14: Week 11 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 13: Homework 5 is now posted
- Nov 7: Week 10 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 3: Week 9 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Oct 31: Homework 3 solution has been updated on Piazza (under Resources) to correct 1(c) and 2(b) solutions
- Oct 31: Homework 4 is now posted
- Oct 30: Midterm exam solution is available on Piazza (under Resources)
- Oct 19: Practice midterm exams have been posted on Piazza (under Resources)
- Oct 19: Homework 3 solution has been posted on Piazza (under Resources)
- Oct 17: During midterm exam, students whose SID ends with 0, 1, 2 or 3 should go to LSB LT2, and other students should go to TYW LT
- Oct 17: Homework 1 and 2 solutions have been posted on Piazza (under Resources)
- Oct 15: Week 6 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Oct 8: Homework 3 is now posted
- Sep 28: Week 4 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 25: Homework 2 is now posted
- Sep 23: There will be a makeup class on Sep 27 (Thu), 6:30pm-8:15pm at TYW LT
- Sep 23: Even though tutorials will run normally on Monday Sep 24, students are encouraged to attend Wednesday tutorials for this week, since some tutorial questions require knowledge from Sep 24 lecture (originally scheduled on Sep 19 and postponed by the super typhoon)
- Sep 19: Week 3 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 18: Despite having no Monday tutorial sessions, Wednesday tutorial sessions will be held as usual. Students who registered for Monday sessions are encouraged to join Wednesday sessions, or study the exercises and solutions after they are posted on Piazza.
- Sep 17: Monday lecture and tutorial sessions are suspended due to super typhoon Mangkhut
- Sep 12: Week 2 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 8: Homework 1 is now posted
Information
- Lectures
- Mon 4:30-6:15pm (TYW LT) Wed 5:30-6:15pm (LSK LT5)
- Tutorials
- Mon 1:30-2:15pm (ERB 712) Mon 3:30-4:15pm (LHC G04) Wed 1:30-2:15 (LSB C2) Wed 4:30-5:15pm (LSB C1)
- Prerequisites
- Discrete math CSCI2110 or ENGG2440
- Textbook
- Introduction to the Theory of Computation, Michael Sipser, 3rd ed (older editions also work and are much cheaper)
- Forum
- Please sign up on Piazza
- Grading
- Homeworks (30%), Midterm exam (30%), Final exam (40%)
To pass this course, getting at least 40 points out of 100 points in the final exam may be required
Lectures
| Date | Topic | Readings | Lectures | Tutorials | Problems | |
|---|---|---|---|---|---|---|
| 1 | Sep 3 | Introduction, finite automata | §1.1 | no tutorial | ||
| 2 | Sep 5 | Nondeterministic finite automata | §1.2 | no tutorial | ||
| 3 | Sep 10 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | HW 1 | |
| 4 | Sep 12 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| Sep 17 | Day after super typhoon Mangkhut | |||||
| 5 | Sep 19 | Text search, closure properties | §1.1-1.3 | week 3 | ||
| 6 | Sep 24 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | week 4 | HW 2 | |
| 7 | Sep 26 | DFA minimization, pumping lemma | §1.4 | |||
| 8 | Sep 27 | Makeup: Context-free grammars | §2.1 | |||
| Oct 1 | Holiday: National Day | no tutorial | ||||
| 9 | Oct 3 | Parsing | §2.1, 7.2 | no tutorial | ||
| 10 | Oct 8 | Pushdown automata | §2.2 | week 6 | HW 3 | |
| 11 | Oct 10 | PDA and CFG conversions | §2.3 | |||
| 12 | Oct 15 | Pumping lemma for CFGs | §2.4 | no tutorial | ||
| Oct 17 | Holiday: Chung Yeung Festival | no tutorial | ||||
| Oct 22 | Midterm exam at TYW LT & LSB LT2 | no tutorial | ||||
| 13 | Oct 24 | LR(0) parser | §2.4 | no tutorial | ||
| 14 | Oct 29 | Church–Turing Thesis | §3.1, 3.2, 3.3 | week 9 | HW 4 | |
| 15 | Oct 31 | Turing machines and their variants | §3.1, 3.2, 3.3 | |||
| 16 | Nov 5 | Decidability | §4.1, 4.2 | week 10 | ||
| 17 | Nov 7 | Undecidability and reductions | §5.1 | |||
| 18 | Nov 12 | Undecidable problems for CFGs | §5.1, 5.2 | week 11 | HW 5 | |
| 19 | Nov 14 | Efficient Turing machines | §7.1, 7.2 | |||
| 20 | Nov 19 | Nondeterministic polynomial time | §7.3, 7.4 | week 12 | ||
| 21 | Nov 21 | NP-completeness | §7.4, 7.5 | |||
| 22 | Nov 26 | Cook–Levin theorem | §7.4, 7.5 | week 13 | HW6 | |
| 23 | Nov 28 | Zero knowledge proofs | §10.4 |
| Date | Topic | Readings | Lectures | Tutorials | Problems | |
|---|---|---|---|---|---|---|
| 1 | Sep 3 | Introduction, finite automata | §1.1 | no tutorial | ||
| 2 | Sep 5 | Nondeterministic finite automata | §1.2 | no tutorial | ||
| 3 | Sep 10 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | HW 1 | |
| 4 | Sep 12 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 17 | Text search, closure properties | §1.1-1.3 | week 3 | ||
| 6 | Sep 19 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | |||
| 7 | Sep 24 | DFA minimization, pumping lemma | §1.4 | week 4 | HW 2 | |
| 8 | Sep 26 | Context-free grammars | §2.1 | |||
| Oct 1 | Holiday: National Day | no tutorial | ||||
| 9 | Oct 3 | Parsing | §2.1, 7.2 | no tutorial | ||
| 10 | Oct 8 | Pushdown automata | §2.2 | week 6 | HW 3 | |
| 11 | Oct 10 | PDA and CFG conversions | §2.3 | |||
| 12 | Oct 15 | Pumping lemma for CFGs | §2.4 | no tutorial | ||
| Oct 17 | Holiday: Chung Yeung Festival | no tutorial | ||||
| Oct 22 | Midterm exam at TYW LT & LSB LT2 | no tutorial | ||||
| 13 | Oct 24 | LR(0) parser | §2.4 | no tutorial | ||
| 14 | Oct 29 | Church–Turing Thesis & Turing machines | §3.1, 3.2, 3.3 | week 9 | HW 4 | |
| 15 | Oct 31 | Decidability | §4.1, 4.2 | |||
| 16 | Nov 5 | Undecidability and reductions | §5.1 | week 10 | ||
| 17 | Nov 7 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 18 | Nov 12 | Efficient Turing machines | §7.1, 7.2 | week 11 | HW 5 | |
| 19 | Nov 14 | Nondeterministic polynomial time | §7.3, 7.4 | |||
| 20 | Nov 19 | NP-completeness | §7.4, 7.5 | week 12 | ||
| 21 | Nov 21 | Cook–Levin theorem | §7.4, 7.5 | |||
| 22 | Nov 26 | Space complexity | §8.1, 8.5, 9.1 | week 13 | HW 6 | |
| 23 | Nov 28 | Zero knowledge proofs | §10.4 |
Tutorials
Tutorial solutions can be found on Piazza after Wed lecture
Homeworks
Homeworks are typically posted on Mondays every other week and due on Thursdays the following week.
Solutions should be submitted to the box labeled CSCI 3130 on the 9th floor of SHB by 11:59pm on Thursday.
Your lowest homework grade will be dropped.
Collaboration on homework is encouraged, but you must write up your own solutions, and list your collaborators on the solution sheet.
- Homework 1 due Thu Sep 20
- Homework 2 due Thu Oct 4 (updated on Sep 26 to refer to the correct pages in Lecture 7 slides)
- Homework 3 due Thu Oct 18
- Homework 4 due Thu Nov 8 (updated Q3 on Nov 3 to correct a minor mistake in the description of Turing machine with left reset)
- Homework 5 due Thu Nov 22
- Homework 6 due 13:59 Mon Dec 10