CSCI 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2011

Instructor
Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926, office hours Fri 10.30-12.30
Teaching Assistants
Chow Chi Wang, cwchow (a) cse.cuhk.edu.hk, SHB 117, office hour Mon 2.30-3.30
Guo Siyao, syguo (a) cse.cuhk.edu.hk, SHB 117, office hour Fri 3.30-4.30
Lee Chin Ho, chlee (a) cse.cuhk.edu.hk, SHB 117, office hour Tue 11-12
Li Fan, fli (a) cse.cuhk.edu.hk, SHB 117, office hour Tue 1.30-2.30

Recent Announcements

13 Dec Please check that all your grades have been entered correctly on moodle. If there is any discrepancy, let us know immediately. (For homework 6 allow until tomorrow.)
13 Dec The final exams have been graded. The median is 64, the deviation 15, the highest score 94, the lowest 30.

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

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

Homework 1 due Thu Sep 22 |
Homework 2 due Mon Oct 10 |
Homework 3 due Fri Oct 21 |
Homework 4 due Thu Nov 10 |
Homework 5 due Tue Nov 29 |
Homework 6 due Thu Dec 8 |

Discussion forums

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

Course Information

Lecture times Mon 4.30-6.15 and Wed 5.30-6.15 in LSB LT6
Tutorials
Li Fan, Tue 12.30-1.15 in ERB 401
Chow Chi Wang, Thu 1.30-2.15 in LHCG04
Lee Chin Ho, Thu 1.30-2.15 in UCC206
Guo Siyao, Fri 2.30-3.15 in ERB 401
Prerequisites Discrete mathematics (CSC 2110). Some programming experience is helpful but not necessary.
Textbook The textbook for this course is Introduction to the Theory of Computation, second edition, by Michael Sipser. It is available in the campus bookstore.
Grading Your grade will be determined from homeworks (30%), a midterm exam (30%), and a final exam (40%).