CSC 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2008

Course Description

Automata theory is the study of abstract computational devices. The purpose of this course is to understand the power and limitations of such devices via rigorous methods. We will study various models including finite automata, grammars, pushdown automata, and Turing machines.

We will develop methods for classifying computational devices according to their computational power, and tools which will allow us to tell if a device is powerful enough to solve a given computational problem.

Tentative schedule

date topic readings lec tut
1Sep 1 Introduction, finite automata §1, 2.2 ppt
2Sep 5 Nondeterministic finite automata §2.3 ppt
3Sep 8 Regular expressions §2.5, 3 ppt ppt
4Sep 12 Properties of regular languages §4.2 ppt
Sep 15 No class, mid-autumn festival ppt
5Sep 19 Limitations of finite automata §4.1 ppt
6Sep 22 DFA minimization §4.4.3 ppt
7Sep 26 More on DFA minimization and equivalence §4.4.2, 4.4.4 ppt
8Sep 29 Context-free languages, parsing §5.1, 5.2, 5.4 ppt pdf
9Oct 3 Normal forms, parsing algorithms §7.1, 7.4.4 ppt
10Oct 6 Pushdown automata §6.1, 6.3 ppt ppt
11Oct 10 Limitations of PDAs §7.2 ppt mp3
12Oct 13 Parsers for programming languages ppt mp3
13Oct 17 Midterm review ppt
Oct 20 Midterm exam ppt
14Oct 24 LR(k) parsers ppt mp3
15Oct 27 The Church-Turing thesis §8.1, 8.2 ppt mp3
16Oct 31 Variants of Turing Machines §8.3, 8.4, 8.6 ppt mp3
17Nov 3 Undecidability §9.1, 9.2 ppt
18Nov 7 More undecidable problems §9.3 (-9.3.3) ppt
19Nov 10 Undecidable problems about CFGs §9.4, 9.5 ppt
20Nov 14 Efficient Turing Machines ppt mp3
21Nov 17 Polynomial time, P and NP §10.1 ppt mp3 ppt
22Nov 21 Reductions, the Cook-Levin Theorem §10.1.5, 10.2 ppt mp3
23Nov 24 NP-complete problems §10.2-10.4 ppt mp3
24Nov 28 Interaction and zero-knowledge ppt
Dec 10 Final exam


Homeworks will be issued on Mondays every other week and will be due within 10 days. You are encouraged to collaborate on them, but you must write up your own solutions and list your collaborators on the solution sheet.

Course Information