CSCI3130: Formal Languages and Automata Theory — Fall 2018

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 3 Introduction, finite automata §1.1 pdf no tutorial
2 Sep 5 Nondeterministic finite automata §1.2 pdf no tutorial
3 Sep 10 NFA to DFA, regular expressions §1.2, 1.3 pdf week 2 HW 1
4 Sep 12 Equivalence of DFA and regular expressions §1.2, 1.3 pdf
Sep 17 Day after super typhoon Mangkhut
5 Sep 19 Text search, closure properties §1.1-1.3 pdf week 3
6 Sep 24 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf week 4 HW 2
7 Sep 26 DFA minimization, pumping lemma §1.4 pdf
8 Sep 27 Makeup: Context-free grammars §2.1 pdf
Oct 1 Holiday: National Day no tutorial
9 Oct 3 Parsing §2.1, 7.2 pdf no tutorial
10 Oct 8 Pushdown automata §2.2 pdf week 6 HW 3
11 Oct 10 PDA and CFG conversions §2.3 pdf
12 Oct 15 Pumping lemma for CFGs §2.4 pdf no tutorial
Oct 17 Holiday: Chung Yeung Festival no tutorial
Oct 22 Midterm exam at TYW LT & LSB LT2 no tutorial
13 Oct 24 LR(0) parser §2.4 pdf no tutorial
14 Oct 29 Church–Turing Thesis §3.1, 3.2, 3.3 pdf week 9 HW 4
15 Oct 31 Turing machines and their variants §3.1, 3.2, 3.3 pdf
16 Nov 5 Decidability §4.1, 4.2 pdf week 10
17 Nov 7 Undecidability and reductions §5.1 pdf
18 Nov 12 Undecidable problems for CFGs §5.1, 5.2 pdf week 11 HW 5
19 Nov 14 Efficient Turing machines §7.1, 7.2 pdf
Tentative schedule
Date Topic Readings Lectures Tutorials Problems
1 Sep 3 Introduction, finite automata §1.1 no tutorial
2 Sep 5 Nondeterministic finite automata §1.2 no tutorial
3 Sep 10 NFA to DFA, regular expressions §1.2, 1.3 week 2 HW 1
4 Sep 12 Equivalence of DFA and regular expressions §1.2, 1.3
5 Sep 17 Text search, closure properties §1.1-1.3 week 3
6 Sep 19 Irregular languages (Myhill–Nerode theorem) Exercise 1.48
7 Sep 24 DFA minimization, pumping lemma §1.4 week 4 HW 2
8 Sep 26 Context-free grammars §2.1
Oct 1 Holiday: National Day no tutorial
9 Oct 3 Parsing §2.1, 7.2 no tutorial
10 Oct 8 Pushdown automata §2.2 week 6 HW 3
11 Oct 10 PDA and CFG conversions §2.3
12 Oct 15 Pumping lemma for CFGs §2.4 no tutorial
Oct 17 Holiday: Chung Yeung Festival no tutorial
Oct 22 Midterm exam at TYW LT & LSB LT2 no tutorial
13 Oct 24 LR(0) parser §2.4 no tutorial
14 Oct 29 Church–Turing Thesis & Turing machines §3.1, 3.2, 3.3 week 9 HW 4
15 Oct 31 Decidability §4.1, 4.2
16 Nov 5 Undecidability and reductions §5.1 week 10
17 Nov 7 Undecidable problems for CFGs §5.1, 5.2
18 Nov 12 Efficient Turing machines §7.1, 7.2 week 11 HW 5
19 Nov 14 Nondeterministic polynomial time §7.3, 7.4
20 Nov 19 NP-completeness §7.4, 7.5 week 12
21 Nov 21 Cook–Levin theorem §7.4, 7.5
22 Nov 26 Space complexity §8.1, 8.5, 9.1 week 13 HW 6
23 Nov 28 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.