2IT70 Automata and Process Theory 2014
(academic year 2013/2014, quartile 4)
News
 August 13
Markings are available for inspection on
Monday August 25 at 15:3016:00 hours and
Thursday September 4 at 13:0013:30 hours,
room MF 7.122 (no appointment needed).
 August 13
An elaboration of the resit of August 13 can be found
here.
 August 5
A preexam meeting is planned for Monday August 11, from 10:45 to 12:30
hours, room MetaForum 15. The idea to discuss the
exam of July 4
and its elaboration and further questions that you may have.
 July 4
An elaboration of the final exam of July 4 can be found
here.
 June 30
A Q&A session to prepare for the exam is scheduled at
Thursday July 3 in MetaForum 15 at 10:45 hours.
Specific questions can be sent by email to the lecturer till
Wednesday noon.
 June 30
Updates of Chapter 3, 4 and 5 of the lecture notes,
incorporating minor changes and small improvements,
are available from the OASE share point of the course.
 June 27
Anonymized results for 2IT73, the classical Turing machine programming
assignment are available
here.
 June 25
An update of Chapter 2 (version 0.3) of the reader is available
in the OASE space of the course.
 June 24
The (anonymized) aggregated results of the clicker tests
of April 28, May 12, May 26, June 2 and June 16
can be found
here.
Please check you mark carefully; for 2IT70 registrants this result
counts for 10% of the FInal mark.
 June 23
The (anonymized) results of the clicker test of Monday June 16 can be
found
here.
 June 18 On Thursday
July 3, there is Q&A session from 10:30 to 12:00 hours,
room to be announced. If you have specific questions for exercises,
constructions or proofs, please send them in by email to the lecturer
Wednesday July 2, 12:00 hours at the latest.
 June 18 On Wednesday
June 25, there are consulation hours for individual questions,
MF 7.122 from 10:30 to 12:00 hours.
 June 18 The
elaboration
of the exemplary exam discussed at Wednesday June 18
is available.
 June 14 The
exemplary exam
that will be discussed on Wednesday June 18 is available.
 June 10 An update of Chapter 5 is
available in the OASE space of the course.
 June 6
The requirements for deliverable 2 of the programming assignment have
been updated: (i) function f now involves addition instead of
multiplication; (ii) function h is now optional, but will lead to a higher
mark (max 8 without h, max 10 for h included); (iii) files need to
be submitted as separate text files.
 June 4
Chapter 5, the final chapter of the reader on labeled transition systems
and bisimulation is available in the OASE space of the course.
 June 3
The (anonymized) results of the clicker test of Monday June 2 can be
found
here.
 May 26
The (anonymized) results of the clicker test of Monday May 26 can be
found
here.
Because of small mistakes in the formulation of canditate answers,
the scores have tuned accordingly.
 May 21
A new release,
release 1.1,
of the cTM NetBeans project is available.
 May 21
There is a bug in the current GUI of the programming assignment
resulting in incorrect resets. A new release will be posted shortly.
You may want to fix the bug in your current code. In the class
classicaltm/gui/OutputToolBar.java you need to replace line 37 by
simulatorTab.getTuringMachine().reset();
simulatorTab.updateValues();
 May 20
The description and auxilliary files for the programming assignment
on simulating and programming the classical Turing machine are
available below.
 May 19
Chapter 3 and an exercise set for section 3.1 have been uploaded to
the OASE space (both for 2IT70/Q4 and 2IT17/Q4).
 May 12
The (anonymized) results of the clicker test of Monday May 12 can be
found
here.
 May 12
Chapter 4 and exercise sets for its sections have been uploaded to
OASE space (both for 2IT70/Q4 and 2IT17/Q4).
Chapter 3 will be discussed and uploaded later.
 April 30
Exercises for Section 2.4, including the homework exercises 2.18
and 2.21, are available on OASE.
 April 30
Exercises for Section 2.3, including the homework exercises 2.13
and 2.14, are available on OASE.
 April 30
The (anonymized) results of the clicker test of Monday April 28 can be
found
here.
 April 24
A
handout belonging to the
first instruction is made available by Rudolf Mak.
 April 23
Slides of the first lectures are available below,
Chapter 2 of the reader and the exercises for section 2.1 are
available from OASE.
 April 22
Lectures start at Wednesday April 23, hours 3+4, AUD 2.
Please bring your clicker or have the vPad app installed
on your smartphone.
 April 22
This course starts at Wednesday April 23 with the instruction at
hours 1+2. The material, Chapter 1 (2it70chapter1.pdf) and the first
set of exercises (2it70exercises.pdf), are from the OASE space of the
course.
 April 22
For the instruction group assignment please consult OASE.
General
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 HBOminor 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.4517.30 (hours 7+8) and Wednesday 10.4512.30 (hours 3+4) in
lecture hall AUD 2, starting Wednesday April 23. Instructions take place at
Mondays 13.4515.30 and Wednesday 8.4510.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.
Literature
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.), AddisonWesley 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 NonDeterministic 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 PushDown Automata 
[slides] 
May 21 
Lectures 8: Section 3.2 ContextFree Grammars 
[slides] 
May 26 
Lectures 9: Section 3.3 Parse Trees 
[slides] 
May 28 
Lectures 10: Section 3.4 ContextFree Languages 
[slides] 
June 2 
Lectures 11: Section 3.5 Properties of ContextFree 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.11.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:
Examination
For students taking the course 2IT70 as part of their Bachelor College
programme or homologation programme (exceptionally) the examination
constituents are as follows:
 Every Monday at the start of the lectures there will be a short clicker
test. Unfortunately, because of network capacity and license issues, only
clickers but not the corresponding app for smartphones (vPad 1.7) can be
used. There will be 6 clicker tests of which the best 5 count. Overall this
will be 10% of the final grade.
 There is a Java programming assignment to implement a
simulator for classical Turing machine programs and to write a couple of
nontrival cTM programs yourself.
The assignment needs to be handed in via Peach, preferably for pairs of
students.
For more details see above.
The programming assignment counts 20% towards the final grade.
 The final examination is scheduled for Friday July 4, 2014 in the morning.
The resit is scheduled for Wednesday August 13, 2014 in the afternoon. The
written examination counts 70% towards the final grade.
For most students in the preMaster program and for Masterstudents 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.