Advanced Automata Theory (CS5236)

The lecturer is Frank Stephan from the Departments of Mathematics and Computer Science of the National University of Singapore.
Frank Stephan's addresses are:

  (1) Department of Mathematics, National University of Singapore
      10 Lower Kent Ridge Road, Block S17, Singapore 119076
      Office: S17#07-04, Telephone +65-6516-2759

  (2) School of Computing, National University of Singpore
      13 Computing Drive, Block COM2, Singapore 117417
      Office: COM2#03-11, Telephone +65-6516-4246

The telefax in the office of the Department of Mathematics is +65-67795452

The email address is

Lecture Notes
The lecture notes are still slightly revised. The current version is made available as a ps-file, pdf-file from pdflatex, pdf-file through ps and latex-file. It covers all topics of the lecture, but is slightly more comprehensive. There are still typing errors which will be corrected and some material not covered by the lecture might be added.

Time and Place
Monday from 18:30 hrs to 20:30 hrs in COM1#02-02,
Tutorial Monday from 20:30 hrs to 21:30 hrs in COM1#02-02.

The tutorial is voluntary, but it is useful to get a better understanding of the material presented. It will provide further examples and also the solutions to selected exercises.

There will be one midterm examination (30 marks) on Monday 03 October 2016 (Week 8 but Lecture 7, as Week 6 has a public holiday) in the second lecture hour. Furthermore each student can reserve with the lecturor exercises; these homeworks the student should write up in the forum. The exercises are found in the slides of the lectures (see below). Students are encouraged to present the chosen homework in the tutorial before they write it up and they can ask the lecturer for help if they do not understand it; once this is done, the write-up in the forum will be graded: a good and comprehensive write-up carries 2 marks; a somewhat correct write-up carries 1 mark. The student can score up to 10 marks by writing up homeworks in the forum. Furthermore the final examination counts 60 marks. As there is one public holiday, there are only 12 lectures in this semester.
The solutions of the final examination are available as ps-file and pdf-file.

Slides and Homework
The slides follow in general the lecture notes and are not so comprehensive. Each week, students can select one homework as marked in the slides and reserve it for writing up in the forum; note that the description of the same homework in the lecture notes might be more comprehensive, therefore please consult the lecture notes as well before doing the homework.
Monday 8 August 2016: Chapter 1 ps-file, pdf-file.
Monday 15 August 2016: Chapter 2 ps-file, pdf-file.
Monday 22 August 2016: Chapter 3 ps-file, pdf-file.
Monday 29 August 2016: Chapter 4 ps-file, pdf-file.
Monday 5 September 2016: Chapter 5 ps-file, pdf-file.
Monday 26 September 2016: Chapter 6 ps-file, pdf-file.
Monday 03 October 2016: Chapter 7 ps-file, pdf-file.
Note that there is a midterm test on Monday 03 October 2016 in the second lecture hour.
Monday 10 October 2016: Chapter 8 ps-file, pdf-file.
Monday 17 October 2016: Chapter 9 ps-file, pdf-file.
Monday 24 October 2016: Chapter 10 ps-file, pdf-file.
Monday 31 October 2016: Chapter 11 ps-file, pdf-file.
Monday 07 November 2016: Chapter 12 ps-file, pdf-file.

Full Automata Theory Manuscript (Combination of CS4232 and CS5236): ps-file, pdf-file through ps, pdf-file by pdflatex.