CSCI3130: Formal Languages and Automata Theory — Fall 2017

Siu On CHAN Office hours Tuesday 2:30-4:30pm SHB 911

Teaching assistants

News

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

Schedule
Date Topic Readings Lectures Tutorials Problems
1 Sep 4 Introduction, finite automata §1.1 pdf no tutorials
2 Sep 6 Nondeterministic finite automata §1.2 pdf no tutorials
3 Sep 11 NFA to DFA, regular expressions §1.2, 1.3 pdf week 2 HW 1
4 Sep 13 Equivalence of DFA and regular expressions §1.2, 1.3 pdf
5 Sep 18 Text search, closure properties §1.1-1.3 pdf week 3
6 Sep 20 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf
Tentative schedule
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.