# CSCI 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2010
• Instructor
Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926, office hours Fri 10.30-12.30
• Teaching Assistants
Hung Chun Ho, chhung (a) cse.cuhk.edu.hk, SHB 1026, office hour Thu 16-17
Guo Siyao, syguo (a) cse.cuhk.edu.hk, SHB 117, office hour Wed 14-15
Li Fan, fli (a) cse.cuhk.edu.hk, SHB 117, office hour Tue 16-17
Yu Yuanming, ymyu (a) cse.cuhk.edu.hk, SHB 606, office hour Wed 2-3

## Recent Announcements

• 28 Dec It was a pleasure to have you in CSCI 3130. Good luck with your studies and I hope to see you in another one of my classes!
• 28 Dec You can check all your grades on moodle. If any grade is registered incorrectly, please let us know as soon as possible.
• 28 Dec The final exams have been graded. The median is 69, the standard deviation is 18.

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

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

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.

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