CSCI 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2010

Recent Announcements

Course Description

Automata theory is the study of abstract computational devices. In this course we introduce rigorous methods that help us understand the power and limitations of such devices. We will study several models including finite automata, grammars, pushdown automata, and Turing machines.

Tentative schedule

date topic readings lecture tutorial
1Sep 6 Introduction, finite automata §1.1 ppt mp3 fa
2Sep 8 Nondeterminism §1.2 ppt mp3 fa
3Sep 13 NFA to DFA, regular expressions §1.2, 1.3 ppt mp3
4Sep 15 RE to DFA conversion §1.3 ppt mp3
5Sep 20 Text search, closure properties §1.1-1.3 ppt mp3
6Sep 22 Pumping lemma §1.4 ppt mp3
7Sep 27 DFA minimization pdf ppt mp3 pdf
8Sep 29 Context-free grammars §2.1 ppt mp3
9Oct 4 Ambiguity, parsing §2.1, 7.2 ppt mp3 ppt
10Oct 6 Pushdown automata §2.2 ppt mp3 jff
11Oct 11 Conversions between CFG and PDA §2.2 ppt mp3 jff ppt
12Oct 13 Pumping lemma for CFGs §2.3 ppt mp3
13Oct 18 LR(0) parsers pdf ppt mp3 pdf
14Oct 20 Midterm exam review
Oct 25 Midterm exam in MMW LT1
15Oct 27 LR(1) parsers pdf ppt mp3
16Nov 1 The Church-Turing thesis §3.1, 3.3 ppt mp3 jff pdf
17Nov 3 Variants of Turing Machines §3.2, pdf ppt mp3
18Nov 8 (Un)decidability §4.1, 4.2 ppt mp3
19Nov 10 Reducibility §5.1 ppt mp3
20Nov 15 Undecidable problems about CFGs §5.1, 5.2 ppt mp3 pdf
21Nov 17 Efficient Turing Machines §7.1, 7.2 ppt mp3
22Nov 22 The class NP, NP-complete problems §7.3, 7.4 ppt ppt
23Nov 24 The Cook-Levin Theorem §7.4 ppt mp3
24Nov 29 More NP-complete problems §7.4, 7.5 ppt mp3
25Dec 1 Interaction and zero-knowledge ppt mp3
Dec 23 Final exam in University Gymnasium


Homeworks will be issued on Mondays every other week and will be due on Thursday the following week. Solutions should be left in the box labeled CSC 3130 on the 9th floor of SHB by 11.59pm on Thursday.

There will be six homeworks. When your final grade is calculated we will drop your lowest homework grade.

You are encouraged to collaborate on homeworks, but you must write up your own solutions and list your collaborators on the solution sheet.

Discussion forums

You can log into the CSCI 3130 discussion forums using your campus ID and CWEM password.

Course Information