2IT70 Automata and Process Theory 2014 (academic year 2013/2014, quartile 4)



This is the webpage of the course 2IT70 as part of the Bachelor Technische Informatica, concerning both the track Software Science (mandatory course) and the track Web Science (optional course). In 2014 this course will be taught in quartile B4. The course is scheduled too for students doing the combined propadeuse Mathematics/Computer Science, the ICT track of Technische Innovatiewetenschappen and Master students Mechanical Engineering.

Students doing the minor Technische Informatica, the HBO-minor BIS, CSE and ES, the schakelprogramma BIS, CSE and ES, as well as Master students BIS, CSE and ES taking 2IT15 or 2IT17 as part of their homologation programme are referred to the webpage of the course taught in quartile 2.

Educational Format Four hours of lectures and four hours instructions. Lectures are scheduled on Mondays 15.45-17.30 (hours 7+8) and Wednesday 10.45-12.30 (hours 3+4) in lecture hall AUD 2, starting Wednesday April 23. Instructions take place at Mondays 13.45-15.30 and Wednesday 8.45-10.30 in MetaForum 06/MetaForum 07 (group Zwaan), MetaForum 13 (group Van de Woude), MetaForum 14 (group Roeloffzen), and MetaForum 15 (group Mak). Group assignments will be announced at OASE.

For a balanced group allotment students are assigned to an instruction group by the student advisor. See the OASE page of this course.


The course material has significantly changed compared to previous year. A new reader will be made available in pdf in the OASE space belonging to the course. The textbook by Hopcroft, Motwani and Ullman, Introduction to Automata Theory, Languages and Computation, (2nd ed.), Addison-Wesley 2001 (or the 3rd edition from 2008 published in paperback) is recommended as background reading. About half of this textbook is covered in the course. Additionally, the course discusses a number of topics from process theory.

Planning Lectures

April 23 Lectures 1: Section 2.1 Deterministic Finite Automata [slides]
April 28 Lectures 2: Section 2.2 Non-Deterministic Finite Automata [slides]
April 30 Lectures 3: Section 2.3 Regular Expressions [slides]
May 7 Lectures 4: Section 2.4 Properties of Regular Languages [slides]
May 12 Lectures 5: Section 4.1 Turing Machines [slides]
May 14 Lectures 6: Section 4.2 Computable Functions [slides]
May 19 Lectures 7: Section 3.1 Push-Down Automata [slides]
May 21 Lectures 8: Section 3.2 Context-Free Grammars [slides]
May 26 Lectures 9: Section 3.3 Parse Trees [slides]
May 28 Lectures 10: Section 3.4 Context-Free Languages [slides]
June 2 Lectures 11: Section 3.5 Properties of Context-Free Languages [slides]
June 4 Lectures 12: Section 5.1 Labeled Transition Systems [slides]
June 11 Lectures 13: Section 5.2 Communicating Processes [slides]
June 16 Lectures 14: Recapitulation [slides]
June 18 Lectures 15: Exemplar Exam [exam]

Planning Classes

April 23 Classes 1: Chapter 1, exercises 1.1-1.7 handout
April 28 Classes 2: Section 2.1, homework 2.1, 2.3, 2.4a  
April 30 Classes 3: Section 2.2, homework 2.8, 2.10, 2.11  
May 7 Classes 4: Section 2.3, homework 2.13, 2.14  
May 12 Classes 5: Section 2.4, homework 2.18, 2.21  
May 14 Classes 6: Section 4.1, homework 4.1, 4.2  
May 19 Classes 7: Section 4.2, homework 4.8  
May 21 Classes 8: Section 3.1, homework 3.1, 3.2ab, 3.3ab  
May 26 Classes 9: Section 3.2, homework 3.5, 3.6  
May 28 Classes 10: Consultation hour  
June 2 Classes 11: Sections 3.3 and 3.4, homework 3.12, 3.13 and 3.15, 3.16  
June 4 Classes 12: Section 3.5, homework 3.18 and 3.19  
June 11 Classes 13: Section 5.1, homework 5.1 and 5.4  
June 16 Classes 14: homework 5.11 and 5.12  

Programming assignment

For the programming assignment on classical Turing machines the following items are available:


For students taking the course 2IT70 as part of their Bachelor College programme or homologation programme (exceptionally) the examination constituents are as follows:

For most students in the pre-Master program and for Master-students taking the course 2IT17, the clicker tests and programming assignment are optional and will not count towards the end result. For these students the written examination counts for 100% to the final degree.

The final written examination is based on the Chapters 2, 3 and 5 of the lectures notes and the exercises discussed at the instructions. Only for a limited number of theorems a proof may be asked: Theorems 2.13, 2.27, 3.20, 3.23, 3.25 and 3.33. To get an idea of what the exam looks like consult the exemplary exam or the exam of July 4, 2014

Lecturer and Tutors

dr. R.H. Mak, MF 6.073, r.h.mak(at)tue.nl
dr. M.J.M. Roeloffzen, MF 6.140, m.j.m.roeloffzen(at)tue.nl
dr. E.P. de Vink, MF 7.122, evink(at)win.tue.nl
dr. J.C.S.P. van der Woude, MF 6.145, japie(at)win.tue.nl
dr. G. Zwaan, MF 7.093, g.zwaan(at)tue.nl

Screencasts for this course

  • No screencast posted.

  • Webpages of the course 2IT70 in 2012/2013.