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:30-16:00 hours and
Thursday September 4 at 13:00-13: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 pre-exam 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 (2it70-chapter1.pdf) and the first
set of exercises (2it70-exercises.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 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.
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.), 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:
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
non-trival 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 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.