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

	date	topic	readings	lecture	tutorial
1	Sep 6	Introduction, finite automata	§1.1	ppt mp3 fa
2	Sep 8	Nondeterminism	§1.2	ppt mp3 fa
3	Sep 13	NFA to DFA, regular expressions	§1.2, 1.3	ppt mp3
4	Sep 15	RE to DFA conversion	§1.3	ppt mp3
5	Sep 20	Text search, closure properties	§1.1-1.3	ppt mp3
6	Sep 22	Pumping lemma	§1.4	ppt mp3
7	Sep 27	DFA minimization	pdf	ppt mp3	pdf
8	Sep 29	Context-free grammars	§2.1	ppt mp3
9	Oct 4	Ambiguity, parsing	§2.1, 7.2	ppt mp3	ppt
10	Oct 6	Pushdown automata	§2.2	ppt mp3 jff
11	Oct 11	Conversions between CFG and PDA	§2.2	ppt mp3 jff	ppt
12	Oct 13	Pumping lemma for CFGs	§2.3	ppt mp3
13	Oct 18	LR(0) parsers	pdf	ppt mp3	pdf
14	Oct 20	Midterm exam review
	Oct 25	Midterm exam in MMW LT1
15	Oct 27	LR(1) parsers	pdf	ppt mp3
16	Nov 1	The Church-Turing thesis	§3.1, 3.3	ppt mp3 jff	pdf
17	Nov 3	Variants of Turing Machines	§3.2, pdf	ppt mp3
18	Nov 8	(Un)decidability	§4.1, 4.2	ppt mp3
19	Nov 10	Reducibility	§5.1	ppt mp3
20	Nov 15	Undecidable problems about CFGs	§5.1, 5.2	ppt mp3	pdf
21	Nov 17	Efficient Turing Machines	§7.1, 7.2	ppt mp3
22	Nov 22	The class NP, NP-complete problems	§7.3, 7.4	ppt	ppt
23	Nov 24	The Cook-Levin Theorem	§7.4	ppt mp3
24	Nov 29	More NP-complete problems	§7.4, 7.5	ppt mp3
25	Dec 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.

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 6 due Thu Dec 9 and solutions
Homework 5 due Thu Nov 25 and solutions
Homework 4 due Thu Nov 11 and solutions
Homework 3 due Thu Oct 21 and solutions
Homework 2 due Thu Oct 7 and solutions
Homework 1 due Fri Sep 24 and solutions

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
Tutorial times Tue 12.30-1.15 in ERB 401, Thu 1.30-2.15 in LHC G04, Fri 2.30-3.15 in ERB 401
Prerequisites Basic familiarity with discrete mathematics (CSC 2110) and programming.
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%).