# 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

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

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.

## 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%).