Automata and process theory (2IT70) (semester A, quartile 2, 2016/2017)

1/2 Text of final exam (2IT71) (27-1-2017) and solution available.
13/1 The final exam (2IT71) is on Friday January 27 9:00-12:00 (location not known yet).
The exam covers
chapter 1,
sections 2.1, 2.2, 2.3, 2.4,
sections 3.1, 3.2, 3.3 (generating and reachable symbols only), 3.4, 3.5, 3.6,
chapter 4,
sections 5.1, 5.2
of the lecture notes.
The exam will contain questions about the theory (definitions, theorems, algorithms
but not the proofs of these) and questions comparable to the exercises and to questions
from the exams of the 2 previous years (see below).
13/1 For your reference the exams from Q2 2014/2015 and Q2 2015/2016 are available:
exam January 23 2015 (2IT71) (solution)
exam April 10 2015 (2IT71) (solution)
exam January 22 2016 (2IT71) (solution)
exam April 8 2016 (2IT71) (solution)
13/1 Text of 2nd interim test (2IT73) and solution available.
9/1 The preliminary results for the interim test 2IT73 can be found on OASE.
On January 10 you can inspect your test at the beginning of the instruction (10:45h) in FLUX 0.01.
A solution to the test will be posted on the webpage after the catchup tests have been done.
The final grades will be reported to the administration after all students have done the test.

The grade was computed as the minimum of 10 and

(points for exercises 1 to 5) * 95/900 + (points for exercise 3)/10.
15/12 On Friday December 23 there will be NO lecture and NO instruction.
14/12 Text of 1st interim test (2IT72) and solution available.
13/12 The second interim test (2IT73) is on Tuesday 20/12 10:45-11:45 in FLUX 0.01.
This is a closed book and obligatory test. Be present on time.
The test covers section 2.4, 3.1, 3.2, 3.3 (generating and reachable symbols only), 3.4, 3.5,
and 3.6 (excluding Theorem 3.54 (Pumping lemma for context-free languages) and following)
of the lecture notes and the corresponding exercises.
It will be assumed that you are familiar with the material from the preceding sections.
The test will contain questions about the theory (definitions, theorems, algorithms, but not proofs of these)
and questions comparable to the exercises or to questions from the tests of the 2 previous years (see below).
13/12 For your reference the text and solutions of the 2nd interim test of the two previous years are available
2nd interim examination 2014 (2IT73) ( solution )
2nd interim examination 2015 (2IT73) ( solution )
8/12 The preliminary results for the interim test 2IT72 can found on OASE.
On December 9 you can inspect your test at the beginning of the instruction (15:45h) in FLUX 0.01.
A solution to the test will posted on the webpage after Wednesday December 14.
The final grades will be reported to the administration after all students have done the test.

The grade was computed as the minimum of 10 and

(points for exercises 1 to 5) * 95/900 + (points for exercise 6)/10.
29/11 Solution available to the problem: if L is regular, then L_c is regular (discussed during the lectures of 22, 25, and 29 november).
28/11 The 1st interim test (2IT72) is on Friday 2/12 13:45-14:45 in FLUX 0.01.
This is a closed book and obligatory test. Be present on time.
The test covers the material from chapter 1 and section 2.1, 2.2, 2.3, and 2.4 (excluding Theorem 2.38 (Pumping lemma for regular languages)) of the lecture notes and the corresponding exercises.
It will contain questions about the theory (definitions, theorems, algorithms, but not proofs of these) and questions comparable to the exercises or to questions from the tests of the 2 previous years (see below).
28/11 For your reference the text and solutions of the two previous years are available
1st interim examination 2014 (2IT72) ( solution )
1st interim examination 2015 (2IT72) ( solution )
lecture/instruction
semester A Quartile 2 Tuesday 1st+2nd hour (lecture) location: FLUX 0.01
Tuesday 3rd+4th hour (instruction) location: FLUX 0.01
Friday 5th+6th hour (lecture) location: FLUX 0.01
Friday 7th+8th hour (instruction) location: FLUX 0.01
lecture notes
lecture notes and excersises will be made available on OASE
examination
1st interim examination (Friday 2/12, 13:45-14:45) (15% of final result)
2nd interim examination (Tuesday 20/12, 10:45-11:45) (15% of final result)
final examination 2IT71 (dates see OASE/OWINFO) (70% of final result, should be at least 5 (Bachelor college rule))
lecturer + instructor
Gerard Zwaan (lecturer/instructor) (MF 6.091, tel. (040 247)4291, e-mail: g.zwaan at tue.nl)
Boris Skoric (instructor) (MF 6.059, tel. (040 247)4870, e-mail: b.skoric at tue.nl)
contents + exercises
week date subject matter (lecture notes) / exercises additional material / solutions
Q2.1 15/11 (1+2)
(lecture)
strings, languages, induction (chapter 1) lecture notes (chapter_1.pdf, OASE)
overview chapter 1
  15/11 (3+4)
(instruction)
exercises 1.0: 1ab, 2, 3a, 4ab, 5(a1,b1,c1,c3,d), 6(a1,b) additional solutions (solutions_1.pdf, OASE)
  18/11 (5+6)
(lecture)
deterministic finite automata (section 2.1) lecture notes (chapter_2.pdf, OASE, corrected section 2.1)
slides section 2.1
example DFA (stepwise construction)
  18/11 (7+8)
(instruction)
exercises 2.1: 1, 2, 3, 4a + 6a, 5, 4b + 6a, 6bc additional solutions (solutions_2.1.pdf, OASE)
Q2.2 22/11 (1+2)
(lecture)
nondeterministic finite automata, NFA-to-DFA transformation (section 2.2) lecture notes (chapter_2.pdf, OASE, corrected section 2.2)
slides section 2.2
  22/11 (3+4)
(instruction)
exercises 2.2: 1, 2, 3, 4, 5
EXTRA: solve ex. 2.1.2(b) by constructing an NFA and applying the NFA-to-DFA algorithm to it
additional solutions (solutions_2.2.pdf, OASE)
  25/11 (5+6)
(lecture)
regular expressions (section 2.3) lecture notes (chapter_2.pdf, OASE, corrected section 2.3)
slides section 2.3
  25/11 (7+8)
(instruction)
exercises 2.3: 1, 2, 4, 5, 6, 7, 8 additional solutions (solutions_2.3.pdf, OASE)
Q2.3 29/11 (1+2)
(lecture)
properties of the class of regular languages (section 2.4) lecture notes (chapter_2.pdf, OASE, corrected section 2.4)
slides section 2.4
pumping lemma usage example
solution: if L is regular than L_c is regular
  29/11 (3+4)
(instruction)
exercises 2.4: 1, 2, 3, 4, 5, 6, 7 additional solutions (solutions_2.4.pdf, OASE)
  2/12
(5: 1st int. test)
(6: lecture)
1st interim test (13:45-14:45): see announcement at the top of the page

lecture (15:00-15:45): push-down automata (section 3.1)
lecture notes (chapter_3.pdf, only section 3.1 is final, OASE)
slides section 3.1
  2/12 (7+8)
(lecture/instruction)
exercises 3.1: 1, 2, 3, 4
(solutions are at the end of chapter 3)
additional solutions (solutions_3.1.pdf, OASE)
Q2.4 6/12 (1+2)
(lecture)
push-down automata (continued) (section 3.1)
context-free grammars (section 3.2)
lecture notes (chapter_3.pdf, only sections 3.1 and 3.2 are final,OASE)
slides section 3.2
  6/12 (3+4)
(instruction)
exercises 3.2: 1, 2, 3, 4, 5, 6 additional solutions (solutions_3.2.pdf, OASE)
  9/12 (5+6)
(lecture)
context-free grammars (continued) (section 3.2)
generating and reachable symbols (section 3.3: useful symbols)
parse trees (section 3.4)
lecture notes (chapter_3.pdf, sections 3.1, 3.2, 3.3, 3.4 are final,OASE)
alternative proof example 3.14 (section 3.2)
slides section 3.3
slides section 3.4
  9/12 (7+8)
(instruction)
exercises 3.3: 1, 4
exercises 3.4: 1, 2, 3
additional solutions (solutions_3.3.pdf, solutions_3.4.pdf, OASE)
Q2.5 13/12 (1+2)
(lecture)
parse trees ((continued) (section 3.4)
class of context-free languages (section 3.5)
lecture notes (chapter_3.pdf, FINAL, OASE)
slides section 3.5
  13/12 (3+4)
(instruction)
exercises 3.5: 1, 2, 3 additional solutions (solutions_3.5.pdf, OASE)
  16/12 (5+6)
(lecture)
properties of context-free languages (section 3.6) slides section 3.6
  16/12 (7+8)
(instruction)
exercises 3.6: 1, 2, 3, 4, 5, 6 additional solutions (solutions_3.6.pdf, OASE)
Q2.6 20/12 (1+2)
(lecture)
reactive Turing machines (section 4.1) lecture notes (chapter_4.pdf,only section 4.1 final,OASE)
slides section 4.1
  20/12
(3: 2nd int. test)
(4: instruction)
2nd interim test (10:45-11:45): see announcement at the top of the page
11:45-12:30: intstruction exercises 4.1: 1, 2, 3, 4, 5
additional solutions (solutions_4.1.pdf,OASE)
  23/12 (5+6)
(NO lecture)
NO LECTURE  
  23/12 (7+8)
(NO instruction)
NO INSTRUCTION  
    Christmas recess  
Q2.7 10/1 (1+2)
(lecture)
classical Turing machines (section 4.2) lecture notes (chapter_4.pdf,OASE)
slides section 4.2
  10/1 (3+4)
(instruction)
exercises 4.2: 1, 2, 3 additional solutions (solutions_4.2.pdf,OASE)
  13/1 (5+6)
(lecture)
labeled transition systems, (branching) bisimulation (section 5.1) lecture notes (chapter_5.pdf, only sections 5.1 and 5.2 final, OASE)
slides section 5.1
  13/1 (7+8)
(instruction)
exercises 5.1: 1-7, 9 additional solutions (solutions_5.1.pdf,OASE)
Q2.8 17/1 (1+2)
(lecture)
branching bisimulation (continued) (section 5.1)
interaction (section 5.2)
mutual exclusion protocol (section 5.3)
alternating bit protocol (section 5.4)
lecture notes (chapter_5.pdf, only sections 5.1 and 5.2 final, OASE)
slides section 5.2
buffers interaction
slides section 5.3 5.4
  17/1 (3+4)
(instruction)
exercises 5.2: 1-5
additional interaction exercise
exercises 5.3: 1
solutions (solutions_5.2_5.3.pdf, OASE)
interaction exercise
interaction solution
  20/1 (5+6)
(instruction, Q&A)
instruction, Q&A  
  20/1 (7+8)
   

Gerard Zwaan