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
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 the textbook; so it is strongly recommended to read them.

Time and Place
Wednesday from 10:00 hrs to 12: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 Lecture 6 (which will be on Wed 20 September 2017 in week 6) and Lecture 11 (which will be on Wed 8 November 2017 in week 12 due to Deepavali being on a Wednesday).
Furthermore, students can score up to 10 marks with homework presentations in tutorials and write-ups, 2 marks per correct presentation and write-up. 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. The exercises are taken from the lecture notes.

About the Textbook by Hopcroft, Motwani and Ullman (slide provided by Pearson).
Here the updated slides for AY 2017/2018.
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.
Solutions of Test (from AY 2015/2016): ps-file and pdf-file.
Solutions of Test (from AY 2017/2018): ps-file and pdf-file.
Lecture 7: ps-file and pdf-file.
Lecture 8: ps-file and pdf-file.
Lecture 9 (in AY2017/2018 in Week 10): ps-file and pdf-file.
Lecture 10 (in AY2017/2018 in Week 11): ps-file and pdf-file.
Lecture 11 (in AY2017/2018 in Week 12): ps-file and pdf-file. Midtermtest Two.
Solutions of Test (from AY 2015/2016): ps-file and pdf-file.
Solutions of Test (from AY 2017/2018): ps-file and pdf-file.
Lecture 12 (in AY2017/2018 in Week 13): ps-file and pdf-file.
Lecture 13: ps-file and pdf-file.
Lecture 13 is left to self-study in AY 2017/2018 due to public holiday; it is not tested in the Final Examination.
Additional Exercises: ps-file and pdf-file.
Solutions of Final Examination (from AY 2015/2016): ps-file and pdf-file.