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