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 (MMW 705)
  • Tue 11:30am-12:15pm (ERB 407)
  • Tue 4:30-5:15pm (BMS LT)
  • Tue 5:30-6:15pm (LC LG23)
Instructor
Siu On CHAN Office hours: Tue 4:30-6:30pm
Teaching assistants
  • Yanbo CHEN ybchen22@cse SHB121A Tue 3:15-4:15
  • Jiahong LIU jhliu22@cse TBA TBA
  • Yijian LU yjlu22@cse TBA TBA
  • 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
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 Asg 1
3 Sep 15 NFA to DFA, regular expressions §1.2, 1.3
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 Asg 2
7 Sep 29 DFA minimization, pumping lemma §1.4
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
Oct 24 Church–Turing Thesis §3.1 week 8
14 Oct 27 Turing machines and their variants §3.2, 3.3
15 Oct 31 Midterm exam no tutorial Asg 4
16 Nov 3 Decidability §4.1, 4.2
17 Nov 7 Undecidability and reductions §5.1 week 10
18 Nov 10 Undecidable problems for CFGs §5.1, 5.2
19 Nov 14 Efficient Turing machines §7.1, 7.2 week 11 Asg 5
20 Nov 17 Nondeterministic polynomial time §7.3, 7.4
21 Nov 21 NP-completeness §7.4, 7.5 week 12
22 Nov 24 Cook–Levin theorem §7.4, 7.5
23 Nov 28 Space complexity §8.1, 8.5, 9.1 week 13 Asg 6
24 Dec 1 Zero knowledge proofs §10.4

Tutorials

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