CSCI3130: Formal Languages and Automata Theory — Fall 2020

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

Siu On CHAN Office hours Tue 2:30-4:30pm (Zoom 959 1001 6123)

Teaching assistants

News

Information

Lectures
Mon 4:30-6:15pm (Zoom 995 9295 6177) Wed 5:30-6:15pm (Zoom 925 9618 7423)
No passcodes, but CUHK-authenticated Zoom accounts are required to join
Tutorials
Tue 9:30-10:15am Tue 10:30-11:15am Tue 4:30-5:15pm Tue 5:30-6:15pm
Zoom 952 4814 0986 (for all tutorial sessions)
Prerequisites
Discrete math CSCI2110 or ENGG2440
Reference book
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 7 Introduction, finite automata §1.1 pdf no tutorial
2 Sep 9 Nondeterministic finite automata §1.2 pdf
3 Sep 14 NFA to DFA, regular expressions §1.2, 1.3 pdf week 2† HW 1
4 Sep 16 Equivalence of DFA and regular expressions §1.2, 1.3 pdf
5 Sep 21 Text search, closure properties §1.1-1.3 pdf week 3‡
6 Sep 23 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf
7 Sep 28 DFA minimization, pumping lemma §1.4 pdf week 4† HW 2
8 Sep 30 Context-free grammars §2.1 pdf
9 Oct 5 Parsing §2.1, 7.2 pdf week 5‡
10 Oct 7 Pushdown automata §2.2 pdf
11 Oct 12 PDA and CFG conversions §2.3 pdf week 6† HW 3
12 Oct 14 Pumping lemma for CFGs §2.4 pdf
13 Oct 19 LR(0) parser §2.4 pdf week 7‡
14 Oct 21 Church–Turing Thesis §3.1 pdf
Oct 26 Holiday: Chung Yueng Festival week 8†
15 Oct 28 Turing machines §3.2, 3.3 pdf
Nov 2 Midterm exam (Zoom 92171517384) no tutorial HW 4
16 Nov 4 Variants of Turing machines §3.2, 3.3 pdf
17 Nov 9 Decidability §4.1, 4.2 pdf week 10‡
18 Nov 11 Undecidability and reductions §5.1 pdf
19 Nov 16 Undecidable problems for CFGs §5.1, 5.2 pdf week 11† HW 5
20 Nov 18 Undecidable problems for CFGs §5.1, 5.2
21 Nov 23 Efficient Turing machines §7.1, 7.2 pdf week 12‡
22 Nov 25 Nondeterministic polynomial time §7.3, 7.4 pdf
23 Nov 30 NP-completeness §7.4, 7.5 pdf week 13† HW 6
24 Dec 2 Cook–Levin theorem §7.4, 7.5 pdf

† Morning sessions: Shiju LIN; Afternoon sessions: Zixing SONG
‡ Morning sessions: Qinghua DING; Afternoon sessions: Wenchao GU

Tentative schedule
Date Topic Readings Lectures Tutorials Problems
1 Sep 7 Introduction, finite automata §1.1 no tutorial
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 (Myhill–Nerode theorem) Exercise 1.48
7 Sep 28 DFA minimization, pumping lemma §1.4 week 4 HW 2
8 Sep 30 Context-free grammars §2.1
9 Oct 5 Parsing §2.1, 7.2 week 5
10 Oct 7 Pushdown automata §2.2
11 Oct 12 PDA and CFG conversions §2.3 week 6 HW 3
12 Oct 14 Pumping lemma for CFGs §2.4
13 Oct 19 LR(0) parser §2.4 week 7
14 Oct 21 Church–Turing Thesis §3.1
Oct 26 Holiday: Chung Yueng Festival week 8
15 Oct 28 Turing machines and their variants §3.2, 3.3
Nov 2 (Online) Midterm exam no tutorial HW 4
16 Nov 4 Decidability §4.1, 4.2
17 Nov 9 Undecidability and reductions §5.1 week 10
18 Nov 11 Undecidable problems for CFGs §5.1, 5.2
19 Nov 16 Efficient Turing machines §7.1, 7.2 week 11 HW 5
20 Nov 18 Nondeterministic polynomial time §7.3, 7.4
21 Nov 23 NP-completeness §7.4, 7.5 week 12
22 Nov 25 Cook–Levin theorem §7.4, 7.5
23 Nov 30 Space complexity §8.1, 8.5, 9.1 week 13 HW 6
24 Dec 2 Zero knowledge proofs §10.4

Tutorials

Tutorial solutions and videos can be found at Piazza → Resources after Tue tutorial sessions

Homeworks

Homeworks are typically posted on Mondays every other week and due on Thursdays the following week

Submit your solution as a single PDF file via Blackboard by 11:59pm on Thursday

You are encouraged to either typeset your solution in LaTeX or Word, or scan or take photos of your handwritten solution (please bundle your scans/photos into a single PDF file)

If you typeset your solution, Graphviz or LaTeX TikZ may help you draw automata: Example 1 and Example 2

Your lowest homework grade (out of 6 assignments) will be dropped

Collaboration on homework is encouraged, but you must write up your own solutions, and list your collaborators on the solution sheet