Theory of Computation (CS3231)

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 telefax in the office of the Department of Mathematics is +65-67795452

The email address is fstephan@comp.nus.edu.sg

Textbooks
The course follows the lecture notes. Nevertheless, feel free to increase the knowledge by reading textbooks on the theory of computation. The most famous textbook is Introduction to Automata Theory, Languages and Computation by John Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (Third Edition, Pearson, 2013, ISBN 1292039051). This textbook has its own Wikipedia Page. Its authors maintain the webpage http://infolab.stanford.edu/~ullman/ialc.html for this book. However, you can also use any other textbook.

Lecture Notes
The lecture notes are available from the following links: ps-file, pdf-file by ps to pdf and pdf-file by pdflatex. The lecture notes reflect the content of the lecture more precisely than any textbook; so it is strongly recommended to read them and to see textbooks only as an add-on.

Lecture: Friday from 10:00 hrs to 12:00 hrs via Zoom.
Tutorials: Tuesday 13:00-14:00 hrs and 14:00-15:00 hrs via Zoom.
Office Hour: Tuesday 09:30-11:00 hrs via Zoom (students who cannot join tutorial groups are encouraged to visit the office hour to present their homeworks).

Check this link for further updates of locations and timings.

Assessment
There will be one midterm test in lecture timings (as there are 13 timeslots this semester). The midterm will count 26 marks and be taken in Week 8 during the normal lecture hours.
Furthermore, students can score up to 14 marks with homework presentations in tutorials and write-ups; each student has to write up and present seven times one homework which is not taken by anyone else in the same tutorial group; students who are from different tutorial groups and have the same question can discuss it among each other, but each one has to make the own write-up in the Forum. Students should in the Forum put the Tutorial group and Question number (T1 or T2 plus T0 for not registered to tutorial) into the header of the post. Students can share their write-up in the Forum over Zoom when presenting the tutorial question.
The final examination will count 60 marks. The overall number of marks obtainable is 100. The exercises are taken from the lecture notes and also copied into the slides. The midterm test will be in the time-slot of the lecture in Week 8.

Slides for AY 2021/2022.
Lecture 1 Friday 13 August 2021: ps-file and pdf-file.
Lecture 2 Friday 20 August 2021: ps-file and pdf-file.
Lecture 3 Friday 27 August 2021: ps-file and pdf-file.
Lecture 4 Friday 03 September 2021: ps-file and pdf-file.
Lecture 5 Friday 10 September 2021: ps-file and pdf-file.
Lecture 6 Friday 17 September 2021: ps-file and pdf-file.
Lecture 7 Friday 01 October 2021: ps-file and pdf-file.
Midterm Test Friday 08 October 2021: Log in through Luminus at 10:00 hrs.
Lecture 8 Friday 15 October 2021: ps-file and pdf-file.
Lecture 9 Friday 22 October 2021: ps-file and pdf-file.
Lecture 10 Friday 29 October 2021: ps-file and pdf-file.
Lecture 11 Friday 5 November 2021: ps-file and pdf-file.
Lecture 12 Friday 12 November 2021: ps-file and pdf-file.

Some sample dfas for some easy tasks with the possibility to input state sequences to be checked.

Solutions of Midterm Tests and Examinations
Solutions of Midterm Test One (from AY 2015/2016): ps-file and pdf-file.
Solutions of Midterm Test One (from AY 2017/2018): ps-file and pdf-file.
Solutions of Midterm Test One (from AY 2019/2020): ps-file and pdf-file.

Solutions of Midterm Test Two (from AY 2015/2016): ps-file and pdf-file.
Solutions of Midterm Test Two (from AY 2017/2018): ps-file and pdf-file.
Solutions of Midterm Test Two (from AY 2019/2020): ps-file and pdf-file.

Solutions of Midterm Test (from AY 2021/2022): ps-file and pdf-file.

Solutions of Final Examination (from AY 2015/2016): ps-file and pdf-file.
Solutions of Final Examination (from AY 2017/2018): ps-file and pdf-file.
Solutions of Final Examination (from AY 2019/2020): ps-file and pdf-file.
Solutions of Final Examination (from AY 2021/2022): ps-file and pdf-file.

Old Slides (for AY 2019/2020).
Note that the slides of Lectures 5 and 6 will be merged into one lecture and that those of the third-last lecture will be expanded. The lectures 7-13 will be renumbered as 6-12.
Lecture 1: ps-file and pdf-file.
Lecture 2: ps-file and pdf-file.
Lecture 3: ps-file and pdf-file.
Some sample dfas for some easy tasks with the possibility to input state sequences to be checked.
Lecture 4: ps-file and pdf-file.
Lecture 5: ps-file and pdf-file.
Lecture 6: ps-file and pdf-file. Midtermtest One.
Lecture 7: ps-file and pdf-file.
Lecture 8: ps-file and pdf-file.
Lecture 9: ps-file and pdf-file.
Lecture 10: ps-file and pdf-file.
Lecture 11: ps-file and pdf-file. Midtermtest Two.
Lecture 12: ps-file and pdf-file.
Lecture 13: ps-file and pdf-file.
Additional Exercises: ps-file and pdf-file.