CSCI3130: Formal Languages and Automata Theory — Fall 2022

News

Information

Lectures
  • Mon 4:30-6:15pm (SC L1)
  • Thu 5:30-6:15pm (SC L1)
Live Zoom lectures: 996 9145 4382
(CUHK-authenticated Zoom account required)
Tutorials
  • Tue 10:30-11:15am (Mong Man Wai Building 705)
  • Tue 11:30am-12:15pm (William MW Mong Engineering Building 407)
  • Tue 4:30-5:15pm (Basic Medical Science Building LT)
  • Tue 5:30-6:15pm (Science Centre LG23) (live Zoom 996 9145 4382)
Instructor
Siu On CHAN Office hours: Mon 2:30-4:30pm
Teaching assistants
  • Yanbo CHEN ybchen22@cse SHB121A Thu 3:15-4:15
  • Jiahong LIU jhliu22@cse SHB1024A Mon 3-4
  • Yijian LU yjlu22@cse SHB1024A Wed 1-2
  • Zixing SONG zxsong@cse SHB1024A Fri 1-2
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
Homework (30%) Midterm exam (30%) Final exam (40%)

Lectures

Schedule
Date Topic Readings Lectures Tutorials Homework
1 Sep 5 Introduction, finite automata §1.1 pdf no tutorial
2 Sep 8 Nondeterministic finite automata §1.2 pdf
Sep 12 Holiday: Day after Mid-Autumn Festival week 2†
3 Sep 15 NFA to DFA, regular expressions §1.2, 1.3 pdf Asg 1
4 Sep 19 Equivalence of DFA and regular expressions §1.2, 1.3 pdf week 3†
5 Sep 23 Text search, closure properties §1.1-1.3 pdf
6 Sep 26 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf week 4†
7 Sep 29 DFA minimization, pumping lemma §1.4 pdf Asg 2
8 Oct 3 Context-free grammars §2.1 pdf no tutorial
9 Oct 6 Parsing §2.1, 7.2 pdf
10 Oct 10 Pushdown automata §2.2 pdf week 6† Asg 3
11 Oct 13 PDA and CFG conversions §2.3 pdf
12 Oct 17 Pumping lemma for CFGs §2.4 pdf week 7†
13 Oct 20 LR(0) parser §2.4 pdf
14 Oct 24 Church–Turing Thesis §3.1 pdf week 8‡
15 Oct 27 Turing machines §3.2, 3.3 pdf
Oct 31 Midterm exam (SC L1 & LSB LT1) no tutorial Asg 4
16 Nov 3 Variants of Turing machines §3.2, 3.3 pdf
17 Nov 7 Decidability §4.1, 4.2 pdf week 10‡
18 Nov 10 Undecidability and reductions §5.1 pdf
19 Nov 14 Undecidable problems for CFGs §5.1, 5.2 pdf week 11‡ Asg 5
20 Nov 17 Efficient Turing machines §7.1, 7.2 pdf
21 Nov 21 Nondeterministic polynomial time §7.3, 7.4 pdf week 12‡
Nov 24 Congregation
22 Nov 28 NP-completeness §7.4, 7.5 pdf week 13‡ Asg 6
23 Dec 1 Cook–Levin theorem §7.4, 7.5 pdf

Lecture recordings can be found at Piazza → Resources

† Morning sessions: Jiahong LIU; Afternoon sessions: Zixing SONG
‡ Morning sessions: Yijian LU; Afternoon sessions: Yanbo CHEN

Tentative schedule
Date Topic Readings Lectures Tutorials Homework
1 Sep 5 Introduction, finite automata §1.1 no tutorial
2 Sep 8 Nondeterministic finite automata §1.2
Sep 12 Holiday: Day after Mid-Autumn Festival week 2
3 Sep 15 NFA to DFA, regular expressions §1.2, 1.3 Asg 1
4 Sep 19 Equivalence of DFA and regular expressions §1.2, 1.3 week 3
5 Sep 23 Text search, closure properties §1.1-1.3
6 Sep 26 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 week 4
7 Sep 29 DFA minimization, pumping lemma §1.4 Asg 2
8 Oct 3 Context-free grammars §2.1 no tutorial
9 Oct 6 Parsing §2.1, 7.2
10 Oct 10 Pushdown automata §2.2 week 6 Asg 3
11 Oct 13 PDA and CFG conversions §2.3
12 Oct 17 Pumping lemma for CFGs §2.4 week 7
13 Oct 20 LR(0) parser §2.4
14 Oct 24 Church–Turing Thesis §3.1 week 8
15 Oct 27 Turing machines §3.2, 3.3
Oct 31 Midterm exam (SC L1 & LSB LT1) no tutorial Asg 4
16 Nov 3 Variants of Turing machines §3.2, 3.3
17 Nov 7 Decidability §4.1, 4.2 week 10
18 Nov 10 Undecidability and reductions §5.1
19 Nov 14 Undecidable problems for CFGs §5.1, 5.2 week 11 Asg 5
20 Nov 17 Efficient Turing machines §7.1, 7.2
21 Nov 21 Nondeterministic polynomial time §7.3, 7.4 week 12
Nov 24 Congregation
22 Nov 28 NP-completeness §7.4, 7.5 week 13 Asg 6
23 Dec 1 Cook–Levin theorem §7.4, 7.5

Tutorials

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

Homework

Homework assignments 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

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

If you submit your assignment late, for every day late, 20 points will be deducted from your submission. Less than a day late is counted as a full day late.

Homework solutions can be found on Piazza