CSCI3130: Formal Languages and Automata Theory — Fall 2021

News

Information

Lectures
  • Mon 4:30-6:15pm (ERB LT)
  • Wed 5:30-6:15pm (ERB LT)
Live Zoom lectures: 996 9145 4382
(CUHK-authenticated Zoom account required)
Tutorials
  • Tue 10:30-11:15am (LSK 210)
  • Tue 11:30am-12:15pm (LSK LT1) (live Zoom 996 9145 4382)
  • Tue 4:30-5:15pm (ELB 405)
  • Tue 5:30-6:15pm (ELB 405)
Instructor
Siu On CHAN Office hours: Tue 3:30-5:30pm
Teaching assistants
  • Shuqing LI sqli21@cse SHB101A Mon 9:00-10:00
  • Jinyang LIU jyliu@cse SHB101A Wed 10:00-11:00
  • Jiahui PAN jhpan21@cse SHB902 Fri 2:30-3:30
  • Tianyu WANG wangty@cse SHB902 Fri 3:30-4:30
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 6 Introduction, finite automata §1.1 pdf no tutorial
2 Sep 8 Nondeterministic finite automata §1.2 pdf
3 Sep 13 NFA to DFA, regular expressions §1.2, 1.3 pdf week 2 Asg 1
4 Sep 15 Equivalence of DFA and regular expressions §1.2, 1.3 pdf
5 Sep 20 Text search, closure properties §1.1-1.3 pdf week 3
Sep 22 Holiday: Day after Mid-Autumn Festival
6 Sep 27 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf week 4 Asg 2
7 Sep 29 DFA minimization, pumping lemma §1.4 pdf
8 Oct 4 Context-free grammars §2.1 pdf week 5
9 Oct 6 Parsing §2.1, 7.2 pdf
10 Oct 11 Pushdown automata §2.2 pdf week 6 Asg 3
Oct 13 Class canceled due to Typhoon Kampasu
11 Oct 18 PDA and CFG conversions §2.3 pdf week 7
12 Oct 20 Pumping lemma for CFGs §2.4 pdf
13 Oct 25 LR(0) parser §2.4 pdf week 8
14 Oct 27 Church–Turing Thesis §3.1 pdf
Nov 1 Midterm exam no tutorial Asg 4
15 Nov 3 Turing machines §3.2, 3.3 pdf
16 Nov 8 Turing machines and their variants §3.2, 3.3 pdf week 10
17 Nov 10 Decidability §4.1, 4.2 pdf
18 Nov 15 Undecidability and reductions §5.1 pdf week 11 Asg 5
19 Nov 17 Undecidable problems for CFGs §5.1, 5.2 pdf
20 Nov 22 Efficient Turing machines §7.1, 7.2 pdf week 12
21 Nov 24 Nondeterministic polynomial time §7.3, 7.4 pdf
22 Nov 29 NP-completeness §7.4, 7.5 pdf week 13† Asg 6

Lecture recordings can be found at Piazza → Resources

† Morning sessions: Shuqing LI; Afternoon sessions: Jinyang LIU
‡ Morning sessions: Jiahui PAN; Afternoon sessions: Tianyu WANG

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

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

Homework solutions can be found on Piazza