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

Note that currently, due to Covid 2019, the lecturer mostly works from home;
therefore use the following email address as the preferred way of contact:
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 slightly more comprehensive. There are still typing errors which will be corrected and some material not covered by the lecture might be added. Furthermore, as there are thirteen weeks of teaching this year, one more chapter for that week will be added; most likely in the second half of the semester.

Time and Place
Tuesday from 18:30 hrs to 20:30 hrs via Zoom,
Tutorial Tuesday from 20:30 hrs to 21:30 hrs via Zoom.

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 29 September 2020 (Week 7 after recess week) in the second lecture hour.
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: Join the tutorial Zoom session and share the screen on Zoom with the homework when explaining it; note that Zoom allows to share any window open on the computer and one can load the homework from the discussion forum into the browser and share it and scroll the window while explaining.

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.

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; furthermore, one week of slides will be added; the new slides will have this year's date.
Tuesday 11 August 2020: Chapter 1 ps-file, pdf-file.

Tuesday 21 August 2018: Chapter 2 ps-file, pdf-file.
Tuesday 28 August 2018: Chapter 3 ps-file, pdf-file.
Tuesday 4 September 2018: Chapter 4 ps-file, pdf-file.
Tuesday 11 September 2018: Chapter 5 ps-file, pdf-file.
Tuesday 18 September 2018: Chapter 6 ps-file, pdf-file.
Tuesday 02 October 2018: Chapter 7 ps-file, pdf-file.
Note that there is a midterm test on Tuesday 02 October 2018 in the second lecture hour.
Tuesday 09 October 2018: Chapter 8 ps-file, pdf-file.
Tuesday 16 October 2018: Chapter 9 ps-file, pdf-file.
Tuesday 23 October 2018: Chapter 10 ps-file, pdf-file.
Tuesday 29 October 2018: Chapter 11 ps-file, pdf-file.
Tuesday 06 November 2018: No lecture, Deepavali.
Tuesday 13 November 2018: 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.