CSCI3130: Formal Languages and Automata Theory — Fall 2017
This is the webpage for a previous offering of the course in 2017; latest offering available here
Siu On CHAN Office hours Tuesday 2:30-4:30pm SHB 911
Teaching assistants
- Hiu Sze CHAM hscham@cse Mon 11:30-12:30 SHB 905
- Minhao LIU mhliu@cse Fri 10-11 SHB 1023
- Xiaotian YU xtyu@cse Thu 11-12 SHB 1024
- Yihan ZHANG yhzhang@cse Wed 9-10 SHB 117
News
- Dec 5: Homework 6 deadline is postponed to Fri Dec 8 17:00
- Nov 29: Week 13 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 27: Homework 6 is now posted
- Nov 22: Week 12 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 16: Week 11 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 16: Homework 5 has been updated to clarify Q1(a), Q1(c), Q2(a), Q2(c)
- Nov 14: Homework 5 is now posted
- Nov 8: Week 10 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 2: Week 9 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 1: Homework 4 Q2 has been updated
- Oct 31: Homework 4 is now posted
- Oct 18: Week 7 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Oct 12: Week 6 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Oct 12: Week 4 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Oct 10: Homework 3 is now posted
- Sep 26: Homework 2 is now posted. Unusual due date & time: Fri Oct 6 13:59
- Sep 20: Week 3 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 20: Week 2 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 11: 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 4 | Introduction, finite automata | §1.1 | no tutorial | ||
| 2 | Sep 6 | Nondeterministic finite automata | §1.2 | no tutorial | ||
| 3 | Sep 11 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | HW 1 | |
| 4 | Sep 13 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 18 | Text search, closure properties | §1.1-1.3 | week 3 | ||
| 6 | Sep 20 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | |||
| 7 | Sep 25 | DFA minimization, pumping lemma | §1.4 | week 4 | HW 2 | |
| 8 | Sep 27 | Context-free grammars | §2.1 | |||
| Oct 2 | Holiday: Day following National Day | no tutorial | ||||
| 9 | Oct 4 | Parsing | §2.1, 7.2 | no tutorial | ||
| 10 | Oct 9 | Pushdown automata | §2.2 | week 6 | HW 3 | |
| 11 | Oct 11 | PDA and CFG conversions | §2.3 | |||
| 12 | Oct 16 | Pumping lemma for CFGs | §2.4 | week 7 | ||
| 13 | Oct 18 | LR(0) parser | §2.4 | |||
| Oct 23 | Midterm exam at LSK LT6 | no tutorial | ||||
| 14 | Oct 25 | Church–Turing Thesis | §3.1, 3.3 | no tutorial | ||
| 15 | Oct 30 | Guest lecture (functional programming) + Turing machines | §3.2 | week 9 | HW 4 | |
| 16 | Nov 1 | Decidability | §4.1, 4.2 | |||
| 17 | Nov 6 | Undecidability and reductions | §5.1 | week 10 | ||
| 18 | Nov 8 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 19 | Nov 13 | Efficient Turing machines | §7.1, 7.2 | week 11 | HW 5 | |
| 20 | Nov 15 | Nondeterministic polynomial time | §7.3, 7.4 | |||
| 21 | Nov 20 | NP-completeness | §7.4, 7.5 | week 12 | ||
| 22 | Nov 22 | Cook–Levin theorem | §7.4, 7.5 | |||
| 23 | Nov 27 | Space complexity | §8.1, 8.5, 9.1 | week 13 | HW 6 | |
| 24 | Nov 29 | Zero knowledge proofs | §10.4 |
| Date | Topic | Readings | Lectures | Tutorials | Problems | |
|---|---|---|---|---|---|---|
| 1 | Sep 4 | Introduction, finite automata | §1.1 | no tutorial | ||
| 2 | Sep 6 | Nondeterministic finite automata | §1.2 | no tutorial | ||
| 3 | Sep 11 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | HW 1 | |
| 4 | Sep 13 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 18 | Text search, closure properties | §1.1-1.3 | week 3 | ||
| 6 | Sep 20 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | |||
| 7 | Sep 25 | DFA minimization, pumping lemma | §1.4 | week 4 | HW 2 | |
| 8 | Sep 27 | Context-free grammars | §2.1 | |||
| Oct 2 | Holiday: Day following National Day | no tutorial | ||||
| 9 | Oct 4 | Parsing | §2.1, 7.2 | no tutorial | ||
| 10 | Oct 9 | Pushdown automata | §2.2 | week 6 | HW 3 | |
| 11 | Oct 11 | PDA and CFG conversions | §2.3 | |||
| 12 | Oct 16 | Pumping lemma for CFGs | §2.4 | week 7 | ||
| 13 | Oct 18 | LR(0) parser | §2.4 | |||
| Oct 23 | Midterm exam at LSK LT6 | no tutorial | ||||
| 14 | Oct 25 | Church–Turing Thesis | §3.1, 3.3 | no tutorial | ||
| 15 | Oct 30 | Guest lecture (functional programming) + Turing machines | §3.2 | week 9 | HW 4 | |
| 16 | Nov 1 | Decidability | §4.1, 4.2 | |||
| 17 | Nov 6 | Undecidability and reductions | §5.1 | week 10 | ||
| 18 | Nov 8 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 19 | Nov 13 | Efficient Turing machines | §7.1, 7.2 | week 11 | HW 5 | |
| 20 | Nov 15 | Nondeterministic polynomial time | §7.3, 7.4 | |||
| 21 | Nov 20 | NP-completeness | §7.4, 7.5 | week 12 | ||
| 22 | Nov 22 | Cook–Levin theorem | §7.4, 7.5 | |||
| 23 | Nov 27 | Space complexity | §8.1, 8.5, 9.1 | week 13 | HW 6 | |
| 24 | Nov 29 | 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 21
- Homework 2 due 13:59 Fri Oct 6
- Homework 3 due Thu Oct 19 (updated on Oct 13 to fix a typo in Q1a)
- Homework 4 due Thu Nov 9 (Q2 updated on Nov 1)
- Homework 5 due Thu Nov 23 (Q1(a), Q1(c), Q2(a), Q2(c) updated for clarification)
- Homework 6 due 17:00 Fri Dec 8