CSCI3130: Formal Languages and Automata Theory — Fall 2016

Siu On CHAN Office hours Tuesday 3-5pm 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 5 Introduction, finite automata §1.1 pdf no tutorials
2 Sep 7 Nondeterministic finite automata §1.2 pdf no tutorials
3 Sep 12 NFA to DFA, regular expressions §1.2, 1.3 pdf week 2 HW 1
4 Sep 14 Equivalence of DFA and regular expressions §1.2, 1.3 pdf
5 Sep 19 Text search, closure properties §1.1-1.3 pdf week 3
6 Sep 21 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf
7 Sep 26 DFA minimization, pumping lemma §1.4 pdf week 4 HW 2
8 Sep 28 Context-free grammars §2.1 pdf
9 Oct 3 Parsing §2.1, 7.2 pdf week 5
10 Oct 5 Pushdown automata §2.2 pdf
Oct 10 Holiday: Chung Yueng Festival no tutorials
11 Oct 12 PDA and CFG conversions §2.2 pdf no tutorials HW 3
12 Oct 17 Pumping Lemma for CFGs §2.3 pdf week 7
13 Oct 19 LR(0) parser §2.4 pdf
Oct 24 Midterm exam no tutorials
14 Oct 26 Church–Turing Thesis §3.1, 3.3 pdf no tutorials
15 Oct 31 Turing machines and their variants §3.2 pdf week 9 HW 4
16 Nov 2 Decidability §4.1, 4.2 pdf
17 Nov 7 Undecidability and reductions §5.1 pdf week 10
18 Nov 9 Undecidable problems for CFGs §5.1, 5.2 pdf
19 Nov 14 Efficient Turing machines §7.1, 7.2 pdf week 11 HW 5
20 Nov 16 Nondeterministic polynomial time §7.3, 7.4 pdf
21 Nov 21 NP-completeness §7.4, 7.5 pdf 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 pdf week 13 HW6
24 Nov 30 Zero-knowledge proofs pdf
Tentative schedule
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)