Advanced Automata Theory (CS5236)

Lecturer
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 following email is read most regularly of all emails assigned to Frank Stephan:
fstephan@comp.nus.edu.sg

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 a bit more comprehensive. There are still typing errors which will be corrected in the case that the lecturer spots these mistakes.

Time and Place
Tuesday from 18:30 hrs to 20:30 hrs in Video Conference Room, SoC.
Tutorial Tuesday from 20:30 hrs to 21:30 hrs at same location.

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

Assessment
There will be one midterm examination (30 marks) on Tuesday 4 October 2022 (Week 8) in the second half of the lecture.

Homeworks follow these regulations:

Create an empty post with the heading "Homework X.Y" having the homework number X.Y from the slides in the discussion forum; reserve at most one homework per week;
Edit and write / Upload as attachment the reserved homework into the post within two weeks or delete the post;
For presentation in the tutorial: Come to the tutorial and explain your solution when it is your turn.

Students can ask the lecturer or classmates for help if they have questions; however, they should do the writing themselves and also try to get the homework out by themselves. Each correct homework counts 1 mark and the maximum marks for assignments is 10 marks.
The final examination counts 60 marks. It is on Wednesday 2 December 2020 from 13:00 to 15:00 hrs Singapore time and is carried out by Zoom. More details can be found in Luminus.

Past Examinations
The solutions of the final examination of 2016 are available as ps-file and pdf-file.
The solutions of the midterm examination of 2018 are available as ps-file and pdf-file.
The solutions of the final examination of 2018 are available as ps-file and pdf-file.
The solutions of the midterm examination in 2020 are available as ps-file and pdf-file.
The solutions of the final examination of 2020 are available as ps-file and pdf-file.
The solutions of the midterm examination in 2022 are available as ps-file and pdf-file.
The solutions of the final examination of 2022 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. The slides below will be reviewed and adjusted to the new date; the current versions are on here on the internet.
Tuesday 16 August 2022: Chapter 1 ps-file, pdf-file.
Tuesday 23 August 2022: Chapter 2 ps-file, pdf-file.
Tuesday 30 August 2022: Chapter 3 ps-file, pdf-file.
Tuesday 06 September 2022: Chapter 4 ps-file, pdf-file.
Tuesday 13 September 2022: Chapter 5 ps-file, pdf-file.
Tuesday 27 September 2022: Chapter 6 ps-file, pdf-file.
Tuesday 04 October` 2022: Chapter 7 ps-file, pdf-file.
Midterm Test in second half of lecture. Revise the lecture material for preparation.
Tuesday 11 October 2022: Chapter 8 ps-file, pdf-file.
Tuesday 18 October 2022: Chapter 9 ps-file, pdf-file.
Tuesday 25 October 2022: Chapter 10 ps-file, pdf-file.
Tuesday 01 November 2022: Chapter 11 ps-file, pdf-file.
Tuesday 08 November 2022: Chapter 12 ps-file, pdf-file.

Full Automata Theory Manuscript (Combination of "Theory of Computation" and "Advanced Automata Theory"): ps-file, pdf-file through ps, pdf-file by pdflatex.