2IT70 Automata and Process Theory 2016

2IT70 Automata and Process Theory 2016 (academic year 2015/2016, quartile 4)

This is the homepage of the course 2IT70 Automata & Process Theory as running in Quartile 4. For the webpage of the 2IT70 course in Quartile 2 as taught by Dr. Gerard Zwaan please go here.

News

August 16 The markings of the resit of August 10 can be seen for all groups with the lecturer on Monday August 22 and Friday August 26, both days from 13:30 to 14:30 hours, room MF 6.075.
August 3 A Q&A session as preparation for the resit of August 10 will be held on Monday August 8, 13:30 hours in MetaForum 6.
July 19 The markings can be seen with Tim Willemse and Gerard Zwaan for students of their tutor groups. Students of the tutor groups of Theo Cats, Rudolf Mak, and Jaap van der Woude can do so on Tuesday August 2 and Thursday August 4, both days from 13:30 to 14:30 hours, room MF 6.075.
June 19 The grade for 2IT73 based on the cTM assignment is available.
June 16 The combined grade for 2IT72 for tutor hours and interim test are available.
June 15 Updates of Chapter 3 and Chapter 5 are available.
June 15 Slides belonging to the exemplary exam are available.
June 13 Update of the formulation of assignment 3b of the exemplar exam.
June 12 On Monday June 13 there will be no lectures. In the lecture slot on Wednesday June 15 the exemplary exam will be made.
June 8 The slides of today's lectures are posted.
June 5 The grading scheme for the cTM programming assignment is described below.
June 1 A document regarding the 5th tutor assignment by Theo Cats can be found here.
June 1 A preliminary version of Chapter 5 is available.
May 29 The attendance for the Q&A session at Thursday evening is rather limited. This activity has been replaced by an office hour on appointment. Please contact the lecturer by email for this.
May 26 The activity in preparation of the tutor meetings of May 30 and June 1 is available below.
May 23 The description of a number of classical Turing machine programs in the assignment have been made more precise, in particular program B6.
May 23 The following results of the interim test have been sent to the student administration.
May 17 The cTM programming assignment is described below.
May 14 Because of Whit Monday and the aim to keep tutor meetings in sync, there will be no tutor meetings on Wednesday May 18.
May 14 Recommended exercises for Section 4.2 are Exercises 4.2.1 and 4.2.2.
May 14 A preliminary version of Chapter 3 is available.
May 9 Slides of the Monday lectures have been added. Recommended exercises for Section 4.1: Exercises 4.1.1, 4.1.2, and 4.1.4. The first part of Chapter 4, containing Sections 4.1 and 4.2, is uploaded too.
May 9 Recommended exercies for Section 2.4: 2.4.22, 2.4.25, and 2.4.27.
May 3 An exemplary interim test is available and will be discussed at the Q&A session on Wednesday May 11, 2016, 17:45 hours in Auditorium 13.
April 25 Slides of the Monday lectures have been added. Recommended exercises for Section 2.3: Exercises 2.3.12, 2.3.13, 2.3.16, and 2.3.18.
April 20 Recommended exercises for Section 2.1 are Exercises 2.1.1 to 2.1.4. For Section 2.1 are these, Exercises 2.2.7, 2.2.8 and 2.2.10.
April 19 A questions & answers session will be held on Thursday evening from April 28 to June 16, 17:45-19:30 hours, room AUD 13 (not on May 5 and May 12).
April 17 Lectures start at Monday April 18 at 15:45 hours. Start of tutor hours differs per tutor group and will be either at the Wednesday April 20 or and Monday April 25.

General

This is the webpage of the course 2IT70 as given in quartile B4, which primarily targets the majors Software Science and Technische Innovatiewetenschappen as well as a number of HBO-TOP programs.

Educational Format Two times two hours of lectures and one time a tutor hour. 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 6 and PAV B1, respectively, starting Monday April 18. On a number of Thursday evenings there is a Q&A session. Tutor hours take place at

Monday 13.45-14:30: group Cats 01 in MultiMedia Paviljoen 2, group Mak 05 in Helix West 3.91, group Willemse 09 in MultiMedia Paviljoen 1, group Van der Woude 13 in Helix West 4.91, group Zwaan 17 in Matrix 146;
Monday 14:45 to 15.30: group Cats 02 in MultiMedia Paviljoen 2, group Mak 06 in Helix West 3.91, group Willemse 10 in MultiMedia Paviljoen 1, group Van der Woude 14 in Helix West 4.91, group Zwaan 18 in Matrix 146;
Wednesday 8.45-9:30: group Cats 03 Helix Oost 1.91, group Mak 07 in Helix West 3.91, group Willemse 11 in Matrix 144, group Van der Woude 15 in Helix West 4.91, group Zwaan 19 in Matrix 146;
Wednesday 9:45-10.30: group Cats 04 Helix Oost 1.91, group Mak 08 in Helix West 3.91, group Willemse 12 in Matrix 1.44, group Van der Woude 16 in Helix West 4.91, group Zwaan 20 in Matrix 146.

Group assignments are available from OASE.

A question & answer session is planned for Thursday evening, starting 17:45 hours, in particular addressing exercises, from Thursday April 28 to Thursday June 16 (but not on May 5 and May 12), room AUD 13.
Because of limited attendance this activity is continued by an office hour on appointment. Contact the lecturer by email for this.

Literature

The course material is undergoing minor revision compared to previous year. An update of the reader will be made available in pdf. 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 for background reading. About half of this textbook is covered in the course. Additionally, the course discusses a number of topics from process theory.

Chapter 1: Preliminaries [pdf]

Chapter 2: Finite Automata and Regular Languages [pdf]

Chapter 3: Push-Down Automata and Context-Free Languages [pdf]

Chapter 4: Turing Machines and Computable Functions [pdf]

Chapter 5: Labeled Transition Systems and Bisimulation [pdf]

Recommended exercises

It is important to practise the theory and techniques discussed in the reader. Students are recommended to do at least the exercises from the reader listed below, and to discuss them with their fellow students. Elaborations of most exercises are available in the reader.

Sec 2.1: Deterministic Finite Automata 2.1.1–2.1.4

Sec 2.2: Finite Automata 2.2.7, 2.2.8, 2.2.10

Sec 2.3: Regular Expressions 2.3.12, 2.3.13, 2.3.16, 2.3.18

Sec 2.4: Regular Languages 2.4.22, 2.4.25, 2.4.27

Sec 3.1: Push-Down Automata 3.1.1, 3.1.2, 3.1.3

Sec 3.2: Context-Free Grammars 3.2.1, 3.2.2

Sec 3.3: Chomsky Normal Form 3.3.2, 3.2.3, 3.3.3

Sec 3.6: Properties of CFL 3.6.2, 3.6.3, 3.6.5, 3.6.6

Sec 4.1: Reactive Turing Machines 4.1.1, 4.1.2, 4.1.4

Sec 4.2: Classical Turing Machines 4.2.1, 4.2.2

Sec 5.1: Bisimulation 5.1.1, 5.1.2, 5.1.4, 5.1.5, 5.1.6

Sec 5.2: Interaction 5.2.1, 5.2.2, 5.2.3

Planning and Slides

April 18 Lectures 1: Section 2.1 Deterministic Finite Automata [slides]

April 20 Lectures 2: Section 2.2 Non-Deterministic Finite Automata [slides]

April 25 Lectures 3: Section 2.3 Regular Expressions [slides]

May 2 Lectures 4: Section 2.4 Properties of Regular Languages [slides]

May 4 Lectures 5: Section 3.1 Push-Down Automata & Section 4.1 Reactive Turing Machines [slides]

May 9 & 11 Lectures 6 & 7: Section 4.2 Classical Turing Machines, extra material on Undecidability [slides]

May 18 Lectures 8: Section 3.2–4 Context-Free Grammars and Parse Trees [slides]

May 23 Lectures 9: Section 3.1 & 3.5 Push-Down Automata and Context-Free Languages [slides]

May 25 Lectures 10: Section 3.6 Properties of CFLs [slides]

May 30 Lectures 11: Section 5.1 Bisimulation [slides]

June 1 Lectures 12: Section 5.2 Interaction [slides]

June 6 Lectures 13: Section 5.3 & 5.4 Mutual Exclusion and Alternating Bit Protocol [slides]

June 8 Lectures 14: Recapitulation [slides]

June 13 No lectures

June 15 Lectures 15: Exemplar Exam [slides]

t.b.m.a.: to be made available

Tutor groups

Each student is alotted to a tutor group. Each tutor group meets once per week with its tutor for one hour. Focus in this meetings is on formal reasoning and proof techniques. Attendance and active participation is considered important and will therefore lead to a mark:

active participation in all seven meetings, mark 10
active participation in six meetings, mark 8
active participation in five meetings, mark 5
active participation in four a less meetings, mark 0

Planning Tutor Group meetings

Wed April 20 & Mon April 25 Do Exercises 1.0.1 and 1.0.3.

Mon May 2 & Wed May 4 Study the proof of Theorem 2.19

Mon May 9 & Wed May 11 Study the Pumping Lemma, its example applications, and do Exercise 2.4.21

Wed May 18 No tutor group meetings

Mon May 23 & Wed May 25 Study Section 4.2 and construct the cTM specified here

Mon May 30 & Wed June 1 Study Sections 3.3 and 3.4 and do the assignment specified here

Mon June 6 & Wed June 8 Study Section 3.6, in particular the application of the Pumping Lemma to show a language is not context-free.

Mon June 13 & Wed June 15 Study Section 5.1 for the notion of branching bisimulation and Section 5.2 for the composition of LTS.
Next do this exercise.

Students are encouraged to meet with their fellow students of their tutor group on the other hours scheduled on Monday 5+6 and Wednesday 1+2 for this course to work on and discuss the exercises.

Interim test

An interim test on a number of techniques covered by Chapter 2 is planned for the evening sitting from 18:45 to 20:30 (hours 9+10) of slot B on Thursday May 12, 2016, taking place in the upper rooms of the Auditorium. More particularly, you are supposed to be able to

give a DFA that accepts a given language and establish the path sets of its states
convert an NFA in a language-equivalent DFA
establish an equivalent regular expression from a DFA
formulate and apply the Pumping Lemma for regular languages.

An exemplary interim test is available that gives an impression would the interim test may look like. On the Wednesday before, May 11, 2016 a Q&A session on the exemplary exam is planned at 17:45 hours in Auditorium 13.

Programming assignment

The programming assignment consists of writing three classical Turing machine programs. Each student has been alloted three subassignments according to the scheme you find here. Contact the lecturer if your student-id doesn't show up.
As an aid a NetBeans8 project containing a simulator for a cTM is available. One may use the simulator to execute example cTM programs D1.ctm and D2.ctm.
Submission via Peach. Deadline Wednesday June 8, 2016.
For grading, each assigned program is tested against 10 input/output pairs by Peach (2 answers are public, 8 answers are hidden). The tests for three programs count for 60%. Furthermore, the programs are inspected on sufficient and adequaat comment. We will use three categories: insufficient, good, very good. This counts for 20%. Finally, the quality of the solutions are assessed regarding transparency and structure, elegancy, efficiency of the underlying algorithm (rather than efficiency in terms of the maximal number of transitions w.r.t. the length of the input), etc.

From Monday May 23 to Wednesday June 8, 2016 a teaching assistant is available for help:

Monday May 23 & 30 and June 6: 11:30-12:30 hours, room MF 5.150
Wednesday May 25 and June 1 & 8: 13:45-14:45 hours, room MF 4.140
Thursday May 26 and June 2: 13:45-14:45 hours, room MF 5.150
Friday May 27 and June 3: 11:30-12:30 hours, room MF 4.140

Examination

The examination of 2IT70 in quartile 4 differs from the installment of 2IT70 in quartile 2.

The interim test on Chapter 2 counts 20% towards the final grade. This test will be held on Thursday May 12 from 18:45-20:30 hours (hours 9+10) in rooms AUD 9 to AUD 16.
Active participation in tutor groups counts 10% towards the final grade.
The weighted combination of the interim test and participation in the tutor groups yields the grade 2IT72 (counting 30% towards the end degree).
The programming assignment on Turing machine programs counts 20% towards the final grade.
The final examination is scheduled for Friday July 1, 2016 in the morning. The resit is scheduled for Wednesday August 10, 2016 in the afternoon. The written examination counts 50% towards the final grade.

The final written examination focusses the Chapters 3 and 5 of the reader. In particular, one is advised to study the proofs of a number of lemmas and theorems (see the slides of June 8 for an exact list). An exemplar exam and the exam of July are available.

Webpages of the course 2IT70 in 2013/2014.

Chapter 1: Preliminaries	[pdf]
Chapter 2: Finite Automata and Regular Languages	[pdf]
Chapter 3: Push-Down Automata and Context-Free Languages	[pdf]
Chapter 4: Turing Machines and Computable Functions	[pdf]
Chapter 5: Labeled Transition Systems and Bisimulation	[pdf]

Sec 2.1: Deterministic Finite Automata	2.1.1–2.1.4
Sec 2.2: Finite Automata	2.2.7, 2.2.8, 2.2.10
Sec 2.3: Regular Expressions	2.3.12, 2.3.13, 2.3.16, 2.3.18
Sec 2.4: Regular Languages	2.4.22, 2.4.25, 2.4.27
Sec 3.1: Push-Down Automata	3.1.1, 3.1.2, 3.1.3
Sec 3.2: Context-Free Grammars	3.2.1, 3.2.2
Sec 3.3: Chomsky Normal Form	3.3.2, 3.2.3, 3.3.3
Sec 3.6: Properties of CFL	3.6.2, 3.6.3, 3.6.5, 3.6.6
Sec 4.1: Reactive Turing Machines	4.1.1, 4.1.2, 4.1.4
Sec 4.2: Classical Turing Machines	4.2.1, 4.2.2
Sec 5.1: Bisimulation	5.1.1, 5.1.2, 5.1.4, 5.1.5, 5.1.6
Sec 5.2: Interaction	5.2.1, 5.2.2, 5.2.3

April 18	Lectures 1: Section 2.1 Deterministic Finite Automata	[slides]
April 20	Lectures 2: Section 2.2 Non-Deterministic Finite Automata	[slides]
April 25	Lectures 3: Section 2.3 Regular Expressions	[slides]
May 2	Lectures 4: Section 2.4 Properties of Regular Languages	[slides]
May 4	Lectures 5: Section 3.1 Push-Down Automata & Section 4.1 Reactive Turing Machines	[slides]
May 9 & 11	Lectures 6 & 7: Section 4.2 Classical Turing Machines, extra material on Undecidability	[slides]
May 18	Lectures 8: Section 3.2–4 Context-Free Grammars and Parse Trees	[slides]
May 23	Lectures 9: Section 3.1 & 3.5 Push-Down Automata and Context-Free Languages	[slides]
May 25	Lectures 10: Section 3.6 Properties of CFLs	[slides]
May 30	Lectures 11: Section 5.1 Bisimulation	[slides]
June 1	Lectures 12: Section 5.2 Interaction	[slides]
June 6	Lectures 13: Section 5.3 & 5.4 Mutual Exclusion and Alternating Bit Protocol	[slides]
June 8	Lectures 14: Recapitulation	[slides]
June 13	No lectures
June 15	Lectures 15: Exemplar Exam	[slides]

Wed April 20 & Mon April 25	Do Exercises 1.0.1 and 1.0.3.
Mon May 2 & Wed May 4	Study the proof of Theorem 2.19
Mon May 9 & Wed May 11	Study the Pumping Lemma, its example applications, and do Exercise 2.4.21
Wed May 18	No tutor group meetings
Mon May 23 & Wed May 25	Study Section 4.2 and construct the cTM specified here
Mon May 30 & Wed June 1	Study Sections 3.3 and 3.4 and do the assignment specified here
Mon June 6 & Wed June 8	Study Section 3.6, in particular the application of the Pumping Lemma to show a language is not context-free.
Mon June 13 & Wed June 15	Study Section 5.1 for the notion of branching bisimulation and Section 5.2 for the composition of LTS. Next do this exercise.