# CSCI3130: Formal Languages and Automata Theory — Fall 2017

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 Thu 10-11 SHB 117

## News

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

2 | Sep 6 | Nondeterministic finite automata | §1.2 | no tutorials | ||

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 |

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

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

2 | Sep 6 | Nondeterministic finite automata | §1.2 | no tutorials | ||

3 | Sep 11 | NFA to DFA, regular expressions | §1.2, 1.3 | 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 | |||

6 | Sep 20 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | |||

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

8 | Sep 27 | Context-free grammars | §2.1 | |||

Oct 2 | Holiday: Day following National Day | no tutorials | ||||

9 | Oct 4 | Parsing | §2.1, 7.2 | no tutorials | ||

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

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

12 | Oct 16 | LR(0) parser | §2.4 | |||

13 | Oct 18 | LR(1) parser | §2.4 | |||

Oct 23 | Midterm exam |
no tutorials | ||||

14 | Oct 25 | Church–Turing Thesis | §3.1, 3.3 | no tutorials | ||

15 | Oct 30 | Guest lecture + Turing machines | §3.2 | HW 4 | ||

16 | Nov 1 | Decidability | §4.1, 4.2 | |||

17 | Nov 6 | Undecidability and reductions | §5.1 | |||

18 | Nov 8 | Undecidable problems for CFGs | §5.1, 5.2 | |||

19 | Nov 13 | Efficient Turing machines | §7.1, 7.2 | HW 5 | ||

20 | Nov 15 | NP-completeness | §7.3, 7.4 | |||

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

22 | Nov 22 | Cook–Levin theorem | §7.4, 7.5 | |||

23 | Nov 27 | Space complexity | §8.1, 8.5, 9.1 | 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