CSCI3130: Formal Languages and Automata Theory — Fall 2019

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

Siu On CHAN Office hours Tue 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
Tue 11:30-12:15pm (ERB LT) Tue 4:30-5:15pm (LSB LT5) Tue 5:30-6:15 (ERB 803) Wed 10:30-11:15 (ERB 408)
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 2 Introduction, finite automata §1.1 pdf video no tutorial
2 Sep 4 Nondeterministic finite automata §1.2 pdf video
3 Sep 9 NFA to DFA, regular expressions §1.2, 1.3 pdf video week 2 HW 1
4 Sep 11 Equivalence of DFA and regular expressions §1.2, 1.3 pdf
5 Sep 16 Text search, closure properties §1.1-1.3 pdf week 3
6 Sep 18 Irregular languages (Myhill–Nerode theorem) Exercise 1.48 pdf
7 Sep 23 DFA minimization, pumping lemma §1.4 pdf week 4 HW 2
8 Sep 25 Context-free grammars §2.1 pdf
9 Sep 30 Parsing §2.1, 7.2 pdf no tutorial
10 Oct 2 Pushdown automata §2.2 pdf
Oct 7 Holiday: Chung Yueng Festival week 6 HW 3
11 Oct 9 PDA and CFG conversions §2.3 pdf
12 Oct 14 Pumping lemma for CFGs §2.4 pdf week 7
13 Oct 16 LR(0) parser §2.4 pdf
Oct 21 Midterm exam at TYW & YIA LT6 no tutorial
14 Oct 23 Church–Turing Thesis §3.1 pdf
15 Oct 28 Turing machines and their variants §3.2, 3.3 pdf week 9 HW 4
16 Oct 30 Decidability §4.1, 4.2 pdf
17 Nov 4 Undecidability and reductions §5.1 pdf week 10
18 Nov 6 Undecidability and reductions
Online lectures
Date Topic Readings Lectures Tutorials Problems
18 Undecidable problems for CFGs §5.1, 5.2 pdf txt
19 Efficient Turing machines §7.1, 7.2 pdf txt week 11
20 Nondeterministic polynomial time §7.3, 7.4 pdf txt
21 NP-completeness §7.4, 7.5 pdf week 12
22 Cook–Levin theorem §7.4, 7.5 pdf
23 Space complexity §8.1, 8.5, 9.1 pdf week 13 HW 6
Tentative schedule
Date Topic Readings Lectures Tutorials Problems
1 Sep 2 Introduction, finite automata §1.1 no tutorial
2 Sep 4 Nondeterministic finite automata §1.2
3 Sep 9 NFA to DFA, regular expressions §1.2, 1.3 week 2 HW 1
4 Sep 11 Equivalence of DFA and regular expressions §1.2, 1.3
5 Sep 16 Text search, closure properties §1.1-1.3 week 3
6 Sep 18 Irregular languages (Myhill–Nerode theorem) Exercise 1.48
7 Sep 23 DFA minimization, pumping lemma §1.4 week 4 HW 2
8 Sep 25 Context-free grammars §2.1
9 Sep 30 Parsing §2.1, 7.2 no tutorial
10 Oct 2 Pushdown automata §2.2
Oct 7 Holiday: Chung Yueng Festival week 6 HW 3
11 Oct 9 PDA and CFG conversions §2.3
12 Oct 14 Pumping lemma for CFGs §2.4 week 7
13 Oct 16 LR(0) parser §2.4
Oct 21 Midterm exam at TYW & YIA LT6 no tutorial
14 Oct 23 Church–Turing Thesis §3.1
15 Oct 28 Turing machines and their variants §3.2, 3.3 week 9 HW 4
16 Oct 30 Decidability §4.1, 4.2
17 Nov 4 Undecidability and reductions §5.1 week 10
18 Nov 6 Undecidable problems for CFGs §5.1, 5.2
19 Nov 11 Efficient Turing machines §7.1, 7.2 week 11 HW 5
20 Nov 13 Nondeterministic polynomial time §7.3, 7.4
21 Nov 18 NP-completeness §7.4, 7.5 week 12
22 Nov 20 Cook–Levin theorem §7.4, 7.5
23 Nov 25 Space complexity §8.1, 8.5, 9.1 week 13 HW 6
24 Nov 27 Zero knowledge proofs §10.4

Tutorials

Tutorial solutions can be found on Piazza after Tue tutorial sessions

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 two 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