Theory of Computation (CS4232)

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

Most of the material of this course will be contained in the textbook 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 for this book.

Lecture Notes
Lecture notes are under preparation. A preliminary version is available as ps-file, pdf-file by ps to pdf and pdf-file by pdflatex.

Time and Place
Thursday from 12:00 hrs to 14:00 hrs in COM1#02-13 (Video Conference Room).

Tutorials are on Monday, from 12:00 to 13:00, from 13:00 to 14:00 and from 14:00 to 15:00 hrs, respectively, in Room COM1#02-08.

There will be two short midterm examinations (20 marks each) in the second half of the lecture on Week 6 and Week 11.
Furthermore, students can score up to 10 marks with homework presentations in tutorials, 4 marks per correct presentation and write-up; joint presentations (each student in a different tutorial group but one joint write-up) give 3 marks each. The write-up has to be published in the discussion forum and has to be correct and sufficiently comprehensive for full marks.
The final examination will count 50 marks. The overall number of marks obtainable is 100.

About the Textbook by Hopcroft, Motwani and Ullman (slide provided by Pearson).
Week 1: ps-file and pdf-file.
Week 2: ps-file and pdf-file.
Week 3: ps-file and pdf-file.
Some sample dfas for some easy tasks with the possibility to input state sequences to be checked.
Week 4: ps-file and pdf-file.
Week 5: ps-file and pdf-file.
Week 6: ps-file and pdf-file. Midtermtest One.
Solutions of Test: ps-file and pdf-file.
Week 7: ps-file and pdf-file.
Week 8: ps-file and pdf-file.
Week 9: ps-file and pdf-file.
Week 10: ps-file and pdf-file.
Week 11: ps-file and pdf-file. Midtermtest Two.
Solutions of Test: ps-file and pdf-file.
Week 12: ps-file and pdf-file.
Week 13: ps-file and pdf-file.
Solutions of Final Examination: ps-file and pdf-file.