CSC 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2009

Recent Announcements

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 several models including finite automata, grammars, pushdown automata, and Turing machines.

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

Tentative schedule

date topic readings lectures tut
1Sep 7 Introduction, finite automata §1.1 ppt mp3 fa
2Sep 11 Nondeterminism §1.2 ppt mp3 fa
3Sep 14 NFA to DFA, regular expressions §1.2, 1.3 ppt ppt
4Sep 18 RE to DFA conversion, text search §1.3 ppt mp3
5Sep 21 Closure properties, pumping lemma §1.4 ppt mp3 ppt pdf
6Sep 25 DFA minimization pdf ppt mp3
7Sep 28 Context-free languages, parsing §2.1 ppt mp3 ppt
8Oct 2 Normal forms, parsing algorithms §2.1+ ppt mp3
9Oct 5 Pushdown automata §2.2 ppt mp3 ppt
10Oct 9 Limitations of pushdown automata §2.3 ppt mp3
11Oct 12 Parsers for programming languages ppt mp3 ppt
12Oct 16 LR(k) parsers ppt mp3
13Oct 19 The Church-Turing thesis §3.1, 3.3 ppt mp3 tm pdf
14Oct 23 Turing Machines and variants §3.2 ppt mp3
Oct 26 No class – Chung Yeung Festival
15Oct 30 Midterm review mp3
Nov 2 Midterm exam
16Nov 6 More variants of Turing Machines §3.2, pdf ppt mp3
17Nov 9 Undecidability §4.1, 4.2 ppt mp3 ppt
18Nov 13 More undecidable problems §5.1, 5.3 ppt mp3
19Nov 16 Undecidable problems about CFGs §5.1, 5.2 ppt mp3 ppt
20Nov 20 Efficient Turing Machines §7.1 ppt mp3
21Nov 23 Polynomial time, P and NP §7.1-7.3 ppt mp3 tm
22Nov 27 Reductions, the Cook-Levin Theorem §7.4 ppt mp3
23Nov 30 NP-complete problems §7.4, 7.5 ppt mp3 ppt
24Dec 4 Interaction and zero-knowledge ppt mp3
Dec 15 Final exam


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

The CSC 3130 discussion forums are accessible from the CUHK campus (or via a VPN connection to CUHK). You need to log in using your campus ID and CWEM password.

Course Information