CSCI3130: Formal Languages and Automata Theory — Fall 2016
This is the webpage for a previous offering of the course in 2016; latest offering available here
Siu On CHAN Office hours Tuesday 3-5pm SHB 911
Teaching assistants
- Minhao LIU mhliu@cse Thursday 11:00am-12:00pm SHB 1023
- Han SHAO hshao@cse Friday 10:00-11:00am SHB 1024
- Feihu ZHANG fhzhang@cse Tuesday 3:45-4:45pm SHB 115
- Hong ZHANG zhangh@cse Wednesday 10:00-11:00am SHB 1026
News
- Dec 10: HW6 solution is now posted on Piazza
- Dec 6: HW6 has been updated to fix a mistake in Q4
- Dec 4: HW6 deadline is now Friday Dec 9 11:59pm (a day after the original deadline)
- Dec 4: Week 13 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Dec 4: HW5 solution is now posted on Piazza
- Dec 4: HW4 solution is now posted on Piazza
- Nov 25: Week 12 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 17: Week 11 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 9: Week 10 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 8: Midterm solution is now posted on Piazza
- Nov 4: Week 9 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 2: Instrutions on reviewing midterm exam papers and making regrade requests are posted on Piazza
- Oct 23: HW3 solution is now posted on Piazza
- Oct 21: Practice midterm exams have been posted on Piazza
- Oct 21: Week 7 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Oct 12: Homework 3 is now posted
- Oct 12: HW2 solution is now posted on Piazza
- Oct 7: Week 5 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 29: Week 4 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 26: Homework 2 is updated; the DFA in Q3 has been changed
- Sep 24: HW1 solution is now posted on Piazza
- Sep 24: Homework 2 is now posted
- Sep 22: Week 3 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 15: Homework 1 is updated with a simplified Q4
- Sep 15: Week 2 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Sep 8: Homework 1 is now posted
- Sep 5: Please sign up on Piazza to join our discussion forum
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 5 | Introduction, finite automata | §1.1 | no tutorials | ||
| 2 | Sep 7 | Nondeterministic finite automata | §1.2 | no tutorials | ||
| 3 | Sep 12 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | HW 1 | |
| 4 | Sep 14 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 19 | Text search, closure properties | §1.1-1.3 | week 3 | ||
| 6 | Sep 21 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | |||
| 7 | Sep 26 | DFA minimization, pumping lemma | §1.4 | week 4 | HW 2 | |
| 8 | Sep 28 | Context-free grammars | §2.1 | |||
| 9 | Oct 3 | Parsing | §2.1, 7.2 | week 5 | ||
| 10 | Oct 5 | Pushdown automata | §2.2 | |||
| Oct 10 | Holiday: Chung Yueng Festival | no tutorials | ||||
| 11 | Oct 12 | PDA and CFG conversions | §2.2 | no tutorials | HW 3 | |
| 12 | Oct 17 | Pumping Lemma for CFGs | §2.3 | week 7 | ||
| 13 | Oct 19 | LR(0) parser | §2.4 | |||
| Oct 24 | Midterm exam | no tutorials | ||||
| 14 | Oct 26 | Church–Turing Thesis | §3.1, 3.3 | no tutorials | ||
| 15 | Oct 31 | Turing machines and their variants | §3.2 | week 9 | HW 4 | |
| 16 | Nov 2 | Decidability | §4.1, 4.2 | |||
| 17 | Nov 7 | Undecidability and reductions | §5.1 | week 10 | ||
| 18 | Nov 9 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 19 | Nov 14 | Efficient Turing machines | §7.1, 7.2 | week 11 | HW 5 | |
| 20 | Nov 16 | Nondeterministic polynomial time | §7.3, 7.4 | |||
| 21 | Nov 21 | NP-completeness | §7.4, 7.5 | week 12 | ||
| 22 | Nov 23 | Cook–Levin theorem | §7.4, 7.5 | Andrej's | ||
| 23 | Nov 28 | Space complexity | §8.1, 8.5, 9.1 | week 13 | HW6 | |
| 24 | Nov 30 | Zero-knowledge proofs |
| Date | Topic | Readings | Lectures | Tutorials | Problems | |
|---|---|---|---|---|---|---|
| 1 | Sep 5 | Introduction, finite automata | §1.1 | no tutorials | ||
| 2 | Sep 7 | Nondeterministic finite automata | §1.2 | no tutorials | ||
| 3 | Sep 12 | NFA to DFA, regular expressions | §1.2, 1.3 | HW 1 | ||
| 4 | Sep 14 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 19 | Text search, closure properties | §1.1-1.3 | |||
| 6 | Sep 21 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | |||
| 7 | Sep 26 | DFA minimization, pumping lemma | §1.4 | HW 2 | ||
| 8 | Sep 28 | Context-free grammars | §2.1 | |||
| 9 | Oct 3 | Parsing | §2.1, 7.2 | |||
| 10 | Oct 5 | Pushdown automata | §2.2 | HW 3 | ||
| Oct 10 | Holiday: Chung Yueng Festival | no tutorials | ||||
| 11 | Oct 12 | Pumping lemma for CFGs | §2.3 | no tutorials | ||
| 12 | Oct 17 | LR(0) parser | §2.4 | |||
| 13 | Oct 19 | LR(1) parser | §2.4 | |||
| Oct 24 | Midterm exam | no tutorials | ||||
| 14 | Oct 26 | Church–Turing Thesis | §3.1, 3.3 | no tutorials | ||
| 15 | Oct 31 | Turing machines and their variants | §3.2 | HW 4 | ||
| 16 | Nov 2 | Decidability | §4.1, 4.2 | |||
| 17 | Nov 7 | Undecidability and reductions | §5.1 | |||
| 18 | Nov 9 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 19 | Nov 14 | Efficient Turing machines | §7.1, 7.2 | HW 5 | ||
| 20 | Nov 16 | NP-completeness | §7.3, 7.4 | |||
| 21 | Nov 21 | More NP-complete problems | §7.4, 7.5 | |||
| 21 | Nov 23 | Cook–Levin theorem | §7.4, 7.5 | |||
| 22 | Nov 28 | Space complexity | §8.1, 8.5, 9.1 | HW 6 | ||
| 23 | Nov 30 | Zero knowledge proofs | §10.4 |
Tutorials
Tutorial solutions can be found on Piazza
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 solutions can be found on Piazza
Homework 1 due Thu Sep 22 (updated on Sep 15 to simplify Q4)
Homework 2 due Thu Oct 6 (Q3 updated on Sep 26)
Homework 3 due Thu Oct 20
Homework 4 due Thu Nov 10
Homework 5 due Thu Nov 24
Homework 6 due Fri Dec 9 (updated on Dec 6 to fix a mistake in Q4)