CSCI 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2011

Recent Announcements

Course Description

Automata theory is the study of abstract computational devices. They have applications in modeling hardware, building compilers, program verification, and so on. 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 5 Introduction, finite automata §1.1 ppt mp3 fa
2Sep 7 Nondeterminism §1.2 ppt mp3 fa
3Sep 12 NFA to DFA, regular expressions §1.2, 1.3 ppt mp3 ppt
4Sep 14 Conversions §1.3 ppt mp3
5Sep 19 Text search, closure properties §1.1-1.3 ppt ppt
6Sep 21 Pumping lemma §1.4 ppt
7Sep 26 DFA minimization pdf ppt mp3
8Sep 28 Context-free grammars §2.1 ppt
9Oct 3 Ambiguity, parsing §2.1, 7.2 ppt mp3 ppt
Oct 5 Chung Yeung festival
10Oct 10 Pushdown automata §2.2 ppt mp3 jff ppt
11Oct 12 Pumping lemma for CFGs §2.3 ppt mp3
12Oct 17 LR(0) parsers pdf ppt mp3 ppt
13Oct 19 LR(1) parsers pdf ppt mp3
Oct 24 Midterm exam
14Oct 26 Midterm exam solutions
15Oct 31 The Church-Turing thesis §3.1, 3.3 ppt mp3 jff ppt
16Nov 2 Variants of Turing Machines §3.2, pdf ppt mp3
17Nov 7 (Un)decidability §4.1, 4.2 ppt mp3 ppt
18Nov 9 Reducibility §5.1 ppt mp3
19Nov 14 More undecidable problems §5.1, 5.2 ppt mp3 ppt
20Nov 16 Efficient Turing Machines §7.1, 7.2 ppt mp3 jff
21Nov 21 The class NP, NP-complete problems §7.3, 7.4 ppt mp3 ppt
22Nov 23 More NP-complete problems §7.4, 7.5 ppt mp3
23Nov 28 The Cook-Levin Theorem §7.4, 7.5 ppt mp3
24Nov 30 Interaction and zero-knowledge ppt
Dec 12 Final exam in John Fulton Centre


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