CSC 3130: Formal languages and automata theory

The Chinese University of Hong Kong, Fall 2009

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 hours Wed 4-6
Li Fan, fli (a) cse.cuhk.edu.hk, SHB 117, office hours Tue 10-12
Wan Haifeng, hfwan (a) cse.cuhk.edu.hk, SHB 121, office hours Fri 3-5
Xiao Linfu, lfxiao (a) cse.cuhk.edu.hk, SHB 506, office hours Thu 2-4

Recent Announcements

15 Dec And this is the end of CSC 3130. Happy holidays and good luck with your studies. It was a pleasure teaching you!
15 Dec All your grades (homeworks, midterm, final) should now be visible on moodle. Please report immediately if there is any discrepancy with your records.
15 Dec The final exams were graded. You can see your grade on moodle. The median is 64 and the standard deviation is 18.
12 Dec Homework 6 has been graded. You can collect yours (and older uncollected homeworks) from SHB 506.

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

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 3 and solutions
Homework 5 due Mon Nov 23 and solutions
Homework 4 due Thu Nov 12 and solutions
Homework 3 due Thu Oct 22 and solutions
Homework 2 due Thu Oct 8 and solutions
Homework 1 due Thu Sep 24 and solutions

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

Lecture times Mon 4.30-6.15 in LSB LT1 and Fri 9.30-10.15 in TYW LT
Tutorial times Tue 12.30-1.15 in LSB LT6, Thu 1.30-2.15 in LSB LT1, and Fri 2.30-3.15 in BMS 1
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%).