Top of this page
Skip navigation, go straight to the content

Automata & Process Theory

This is the web page for the course on automata and process theory given in Semester B of 2009/2010. The subject code of the course is 2IT15 (or 2IT17 for Master students). For details about the course (precise schedule, prior knowledge, learning objectives, contents etc.) see the OWInfo page.

News

  • Mon 28-06-2010: The final exam is on Friday, 2 Juli 2010, 9:00—12:00 in VRT 4.05 and VRT 4.11; covered material: Chapter 1—5.4.
  • Mon 14-06-2010: The grades of the second assignment are available online. You can pick-up the graded assignment, with feedback, at the next instruction on Tuesday (15-06-2010).
  • Wed 02-06-2010: Check out this YouTube movie of a Turing machine made with LEGO built by students from Aarhus University!
  • Fri 28-05-2010: Two handouts are made available today:
  • Wed 26-05-2010: To decrease the load of simultaneous assignments, the deadline of the second assignment has been postponed until Friday, 4 June 2010.
  • Tue 25-05-2010: Corrected hand-in deadline in the PDF and on this web page to Monday, 31 May 2010.
  • Fri 22-05-2010: Second assignment is available from this web page. Read more about it below. Hand-in deadline: Monday, 31 May 2010!
  • Fri 21-05-2010: Second assignment will be online tonight or tomorrow (Sat 22-05-2010)!
  • Mon 19-04-2010: The instruction on Friday, 23 April 2010 in MA 1.60 by Jeroen Keiren is moved to the instruction in LP -1.19 by Wieger Wesselink due to Jeroen’s absence!
  • Fri 16-04-2010: The exams have been graded and the grades have been passed on to the administration. In the upcoming instruction the marked exams will be returned to you.
  • Mon 29-03-2010: The mid-term exam is on Tuesday, 6 April 2010, 14:00—15:30 in VRT 4.05 and VRT 4.11; covered material: Chapter 1—3.3.
  • Mon 22-03-2010: The grades of the first assignment are available online.
  • Mon 15-03-2010: Added old exams.
  • Fri 05-03-2010: First assignment is available from this web page. Read more about it below. Hand-in deadline: Wednesday, 17 March 2010!
  • Thu 04-02-2010: For those who are interested, check out this presentation about visualising transition systems by Hannes Pretorius from the visualisation group.
  • Mon 01-02-2010: Started updating the schedule and instructions information as the course goes along.
  • Tue 26-01-2010: Initial information about the course available on this web page.

Course Information

The main lecturer of the course is: prof. Jos Baeten

The instructions are given by (rooms on Monday and Friday):

  1. Roel Bloo (in PAV j0.17 (Mon), HG 6.09 (Fri))
  2. Paul van Tilburg (in PAV u0.46 (Mon), NL a2.29 (Fri))
  3. Jeroen Keiren (in MA 1.43 (Mon), MA 1.60 (Fri))
  4. Wieger Wesselink (in PAV b0.2 (Mon), LP -1.19 (Fri))

Group 1 is meant for 1st year students that have Roel Bloo as mentor;
Group 2 for 1st year students that have Pieter Cuijpers as mentor;
Group 3 for other students that prefer to have instructions in English;
Group 4 for other students that prefer to have instructions in Dutch.

The syllabus of this course is the (January 4, 2010) draft version of the textbook “Models of Computation: Automata and Processes” by J.C.M. Baeten. It is for sale at the ‘Dictatenverkoop’ and available as PDF here.
N.B. Please make sure you use the correct version! Chapters 4 and 5 have been changed extensively since the 2009 version. However, the 2009 version can still be used during Quartile 3.

Schedule

Every week there will be a lecture on Thursday and instruction on Friday. On Mondays the slot alternates between lecture and instruction. Every odd week there is an instruction and every even week there is a lecture on Monday, with exception of the first two weeks when the situation is reversed. See also this class dates part of the OWInfo page for a precise overview of the lecture and instruction dates.

The course lectures follow the following schedule:

Semester B Quartile 3

  • Chapter 1: Introduction
    • Mon 01-02-2010: Entire chapter
  • Chapter 2: Finite Automata
    • Thu 04-02-2010: Section 2.1
    • Thu 11-02-2010: Section 2.2 and 2.3
    • Mon 22-02-2010: Section 2.4
    • Thu 25-02-2010: Section 2.4 and 2.5
    • Thu 04-03-2010: Section 2.5—2.7
    • Mon 08-03-2010: Section 2.7 and 2.8
    • Thu 11-03-2010: Section 2.8 and a small peek into Chapter 3
  • Chapter 3: Extending the Algebra
    • Thu 18-03-2010: Section 3.1
    • Mon 22-03-2010: Section 3.2
    • Thu 25-03-2010: Section 3.3
    • Thu 01-04-2010: Practice for mid-term exam

Semester B Quartile 4

  • Chapter 3: Extending the Algebra
    • Mon 19-04-2010: Section 3.5 and a small peek into Chapter 4
  • Chapter 4: Push-Down Automata
    • Thu 22-04-2010: Section 4.1 and 4.2
    • Thu 29-04-2010: Section 4.2 and 4.3
    • Mon 03-05-2010: Section 4.3 and 4.4
    • Thu 06-05-2010: Section 4.4 and 4.5
    • Mon 17-05-2010: Section 4.6
    • Thu 20-05-2010: Section 4.7
    • Thu 27-05-2010: Section 4.8
  • Chapter 5: Computability and Executability
    • Mon 31-05-2010: Section 5.1
    • Thu 03-06-2010: Section 5.2 and 5.3
    • Thu 10-06-2010: Section 5.4 and 5.5
    • Mon 14-06-2010: Overview of the course material
    • Thu 17-06-2010: Practice for final exam

Instructions

Depending on the week there are one or two instructions. See the Schedule section above for the exact details. Each week one assignment will be marked as homework (using bold in the list below), giving you the chance to hand it in and get feedback. The homework assignment will be announced at the end of the instruction on Friday. You can hand it in until the following Wednesday and it will be returned to you with feedback on Friday thereafter.

List of exercises

  • Fri 05-02-2010: 1.0.1—1.0.3, 2.1.1—2.1.3, 2.1.4(ab), 2.1.5, 2.1.6, 2.1.7
  • Mon 08-02-2010: 2.1.9, 2.1.10, 2.1.15, 2.1.17—2.1.21
  • Fri 12-02-2010: 2.2.2, 2.3.1—2.3.4, 2.3.5, 2.3.6, 2.3.7
  • Fri 26-02-2010: 2.4.1—2.4.5, 2.4.6, 2.4.7—2.4.11, 2.4.12(a), 2.4.13
  • Mon 01-03-2010: 2.5.1—2.5.7(a)
  • Fri 05-03-2010: 2.5.8, 2.5.10—2.5.12, 2.6.1, 2.6.2, 2.6.3, 2.6.4, 2.6.5
  • Fri 12-03-2010: 2.7.1—2.7.3
  • Mon 15-03-2010: 2.8.1—2.8.4(a—c), 2.8.4(d)
  • Fri 19-03-2010: 3.1.1, 3.2.1, 3.2.3, (3.2.2)
  • Mon 29-03-2010: 3.2.2, 3.2.4, (3.2.6), 3.2.7, 3.3.1, 3.3.2, 3.3.5, 3.3.6, 3.3.11
  • Fri 23-04-2010: 3.4.1, 3.5.1, 3.5.2 (+ show bisimilar to buffer with capacity 1), 4.1.1
  • Mon 26-04-2010: 4.1.3, 4.1.4, 4.1.5, 4.1.7, 4.2.1, 4.2.2, 4.2.4, 4.2.4, 4.2.5, (4.2.9) (hand-in assignment: draw a push-down automaton for L = { w | #a(w) = 2 #b(w) } with A = { a, b })
  • Fri 07-05-2010: 4.2.11, 4.2.10, 4.2.13, 4.2.14
  • Mon 10-05-2010: 4.3.1—4.3.6, 4.4.1—4.4.4, 4.4.5
  • Fri 21-05-2010: 4.4.10, 4.4.11, 4.5.5, 4.5.6 (non-deterministic case), apply the construction of Theorem 4.52 to the push-down automaton for the language of 4.2.10(b), apply the construction of Theorem 4.53 on the push-down automaton in Figure 4.5 (N.B. the restrictions can be dropped if appropriate modifications are made).
  • Fri 28-05-2010: 4.6.1, 4.6.3, (4.6.2), 4.7.3(a—c), 4.7.4(c), 4.7.5
  • Fri 04-06-2010: 4.8.1—4.8.3, (4.8.4), 4.8.6
  • Mon 07-06-2010: 5.1.1—5.1.5, 5.1.7, 5.1.6
  • Fri 11-06-2010: 5.1.8, 5.4.3

Assignments

Besides the mid-term and final exams there will be two assignments which will contribute to the final grade. One assignment will be given halfway Quartile 3 and the other halfway Quartile 4. The assignments will be handed out during the instructions and are also available via this web page (below). Once posted you will have over a week to do the assignment (separately from each other) and hand it in using the usual channels (via you instructor).

If there are any questions about the assignments or the grades (e.g. you are not on the list), please contact your instructor.

Examination & Grades

There will be two closed-book exams:

  1. a mid-term exam (1.5h, 25% of the grade) about Chapter 1—3.3 after Quartile 3 (2XT15),
  2. a final exam (3h, 50% of the grade) about Chapter 1—5.4 after Quartile 4 (2YT15),

that determine 75% in total of the grade.

Additionally, there will be two assignments that together constitute the remaining 25% of the grade. One assignments will be given halfway Quartile 3 and the other halfway Quartile 4, each (naturally) worth 12.5% of the grade.

The reexamination in August will cover the entire material and not take any previous assignments and exams into account and is thus worth 100% of the grade.

Old exams

Note that the chapter indications of covered material are just approximations because both the schedule and the study material have been changed over the years!

Agenda