**Lectures**Mon 4.30-6.15 in MMW LT2 and Fri 9.30-10.15 in LSB LT6**Instructor**Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 109, phone 31634261**Office hour**Fri 11-12 or by appointment**Tutorial times**Tue 12.30-1.15 in LSB LT6, Thu 1.30-2.15 in LSB LT3, Fri 2.30-3.15 in BMS 2**Teaching Assistants**

Tu Shikui, sktu (a) cse.cuhk.edu.hk, SHB 905, office hour Thu 2.30-3.30

Shi Lei, shil (a) cse.cuhk.edu.hk, SHB 905, office hour Tue 10-11

Bridge Q. Zhao, qzhao (a) cse.cuhk.edu.hk, SHB 120, office hour Wed 2-3

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 various models including finite automata, grammars, pushdown automata, and Turing machines.

We will develop methods for classifying computational devices according to their computational power, and tools which will allow us to tell if a device is powerful enough to solve a given computational problem.

date | topic | readings | lec | tut | |
---|---|---|---|---|---|

1 | Sep 1 | Introduction, finite automata | §1, 2.2 | ppt | |

2 | Sep 5 | Nondeterministic finite automata | §2.3 | ppt | |

3 | Sep 8 | Regular expressions | §2.5, 3 | ppt | ppt |

4 | Sep 12 | Properties of regular languages | §4.2 | ppt | |

Sep 15 | No class, mid-autumn festival |
ppt | |||

5 | Sep 19 | Limitations of finite automata | §4.1 | ppt | |

6 | Sep 22 | DFA minimization | §4.4.3 | ppt | |

7 | Sep 26 | More on DFA minimization and equivalence | §4.4.2, 4.4.4 | ppt | |

8 | Sep 29 | Context-free languages, parsing | §5.1, 5.2, 5.4 | ppt | |

9 | Oct 3 | Normal forms, parsing algorithms | §7.1, 7.4.4 | ppt | |

10 | Oct 6 | Pushdown automata | §6.1, 6.3 | ppt | ppt |

11 | Oct 10 | Limitations of PDAs | §7.2 | ppt mp3 | |

12 | Oct 13 | Parsers for programming languages | ppt mp3 | ||

13 | Oct 17 | Midterm review | ppt | ||

Oct 20 | Midterm exam |
ppt | |||

14 | Oct 24 | LR(k) parsers |
ppt mp3 | ||

15 | Oct 27 | The Church-Turing thesis | §8.1, 8.2 | ppt mp3 | |

16 | Oct 31 | Variants of Turing Machines | §8.3, 8.4, 8.6 | ppt mp3 | |

17 | Nov 3 | Undecidability | §9.1, 9.2 | ppt | |

18 | Nov 7 | More undecidable problems | §9.3 (-9.3.3) | ppt | |

19 | Nov 10 | Undecidable problems about CFGs | §9.4, 9.5 | ppt | |

20 | Nov 14 | Efficient Turing Machines | ppt mp3 | ||

21 | Nov 17 | Polynomial time, P and NP | §10.1 | ppt mp3 | ppt |

22 | Nov 21 | Reductions, the Cook-Levin Theorem | §10.1.5, 10.2 | ppt mp3 | |

23 | Nov 24 | NP-complete problems | §10.2-10.4 | ppt mp3 | |

24 | Nov 28 | Interaction and zero-knowledge | ppt | ||

Dec 10 | Final exam |

Homeworks will be issued on Mondays every other week and will be
due within 10 days. You are encouraged to collaborate on them, but
you *must* write up your own solutions and list your
collaborators on the solution sheet.

- Homework 6 due Thu Nov 27
- Homework 5 due Thu Nov 13
- Homework 4 due Fri Oct 31
- Homework 3 due Thu Oct 16
- Homework 2 due Thu Oct 2
- Homework 1 due Thu Sep 18

**Prerequisites**Basic familiarity with discrete mathematics (CSC 2110) and programming.**Textbook**The textbook for this course is*Introduction to Automata Theory, Languages, and Computation*, 3rd edition, by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman.**Grading**Your grade will be determined from class attendance (10%), homeworks (30%), a midterm exam (20%), and a final exam (40%).