## CSCI3130: Formal Languages and Automata Theory

Fall 2015 This is the webpage for a previous offering of the course in 2015; latest offering available here

Siu On CHAN Tuesday & Thursday 3-4pm SHB 911

Teaching assistants

- Fu Yang HUANG fyhuang@cse Friday 2:00-3:00pm SHB 1026
- Baoxiang WANG bxwang@cse Monday 1:30-2:30pm SHB 117
- Feihu ZHANG fhzhang@cse Tuesday 4:30-5:30pm SHB 115
- Hong ZHANG zhangh@cse Friday 10:00-11:00am SHB 1026

### News

- Dec 7: Week 13 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 29: Homework 6 is now posted. Note that it is due on Wednesday, a day earlier than usual.
- Nov 25: Week 12 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 19: Week 11 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 17: Homework 5 is now posted
- Nov 11: Week 10 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 4: Week 9 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
- Nov 3: Homework 4 is now posted
- Nov 3: Midterm solution is now posted on Piazza. For regrade request, please see the Piazza post
- Oct 24: HW3 solution is now posted on Piazza
- Oct 23: Practice midterm 1 and 2 have been posted on Piazza

### Information

- Lectures
- Mon 4:30-6:15pm (TYW LT) Wed 5:30-6:15pm (LSK LT5)
- Tutorials
- Mon 2:30-3:15pm (LSK LT5) Mon 3:30-4:15pm (LSK 301) Tue 3:30-4:15 (LSB G35) Wed 4:30-5:15pm (SC L1)
- 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%)

### Lectures

Date | Topic | Readings | Lectures | Tutorials | Problems | |
---|---|---|---|---|---|---|

1 | Sep 7 | Introduction, finite automata | §1.1 | no tutorials | ||

2 | Sep 9 | Nondeterministic finite automata | §1.2 | |||

3 | Sep 14 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | HW 1 | |

4 | Sep 16 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||

5 | Sep 21 | Text search, closure properties | §1.1-1.3 | week 3 | ||

6 | Sep 23 | Irregular languages | Exercise 1.48 | |||

Sep 28 | Holiday: the day after Mid-Autumn | no tutorials | ||||

7 | Sep 30 | DFA minimization, pumping lemma | §1.4 | HW 2 | ||

8 | Oct 5 | Context-free grammars | §2.1 | week 5 | ||

9 | Oct 7 | Parsing | §2.1, 7.2 | |||

10 | Oct 12 | Pushdown automata | §2.2 | week 6 | HW 3 | |

11 | Oct 14 | Pumping lemma for CFGs | §2.3 | |||

12 | Oct 19 | LR(k) parsers | §2.4 | no tutorials | ||

Oct 21 | Holiday: Chung Yeung Festival | |||||

Oct 26 | Midterm exam |
no tutorials | ||||

13 | Oct 28 | Church–Turing Thesis | §3.1, 3.3 | |||

14 | Nov 2 | Turing machines and their variants | §3.2 | week 9 | HW 4 | |

15 | Nov 4 | Decidability | §4.1, 4.2 | |||

16 | Nov 9 | Undecidability and reductions | §5.1 | week 10 | ||

17 | Nov 11 | Undecidable problems for CFGs | §5.1, 5.2 | |||

18 | Nov 16 | Efficient Turing machines | §7.1, 7.2 | week 11 | HW 5 | |

19 | Nov 18 | Nondeterministic polynomial time | §7.3, 7.4 | |||

20 | Nov 23 | NP-completeness | §7.4, 7.5 | week 12 | ||

21 | Nov 25 | Cook–Levin theorem | §7.4, 7.5 | Andrej's | ||

22 | Nov 30 | Space complexity | §8.1, 8.5, 9.1 | week 13 | HW6 | |

23 | Dec 2 | Zero-knowledge proofs |

Date | Topic | Readings | Lectures | Tutorials | Problems | |
---|---|---|---|---|---|---|

1 | Sep 7 | Introduction, finite automata | §1.1 | no tutorials | ||

2 | Sep 9 | Nondeterministic finite automata | §1.2 | |||

3 | Sep 14 | NFA to DFA, regular expressions | §1.2, 1.3 | HW 1 | ||

4 | Sep 16 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||

5 | Sep 21 | Text search, closure properties | §1.1-1.3 | |||

6 | Sep 23 | Myhill–Nerode theorem | Handout | |||

Sep 28 | Holiday: the day after Mid-Autumn | no tutorials | ||||

7 | Sep 30 | DFA minimization | Handout | HW 2 | ||

8 | Oct 5 | Context-free grammars | §2.1 | |||

9 | Oct 7 | Ambiguity, parsing | §2.1, 7.2 | |||

10 | Oct 12 | Pushdown automata | §2.2 | HW 3 | ||

11 | Oct 14 | Pumping lemma for CFGs | §2.3 | |||

12 | Oct 19 | LR(k) parsers | §2.4 | no tutorials | ||

Oct 21 | Holiday: Chung Yeung Festival | |||||

Oct 26 | Midterm exam |
no tutorials | ||||

13 | Oct 28 | Turing machines | §3.1, 3.3 | |||

14 | Nov 2 | Variants of Turing machines | §3.2 | HW 4 | ||

15 | Nov 4 | Undecidability | §4.1, 4.2 | |||

16 | Nov 9 | Reductions | §5.1 | |||

17 | Nov 11 | Rice theorem, more undecidable problems | §5.1, 5.2 | |||

18 | Nov 16 | Efficient Turing machines | §7.1, 7.2 | HW 5 | ||

19 | Nov 18 | NP-completeness | §7.3, 7.4 | |||

20 | Nov 23 | More NP-complete problems | §7.4, 7.5 | |||

21 | Nov 25 | NL-completeness, Savitch's theorem | §8.2, 8.5 | |||

22 | Nov 30 | Hardness of approximation | Handout | HW 6 | ||

23 | Dec 2 | Zero knowledge proofs | Handout |

### 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 24

Homework 2 due Thu Oct 8

Homework 3 due Thu Oct 22 (last updated on Oct 20)

Homework 4 due Thu Nov 12

Homework 5 due Thu Nov 26

Homework 6 due Wed Dec 9