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
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
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
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:
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
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:
Examination
The examination of 2IT70 in quartile 4 differs from the installment of 2IT70 in quartile 2.
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.