**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 115/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.222/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 itadditional 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.325/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 regular29/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, , OASE)*only section 3.1 is final*

slides section 3.12/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*

slides section 3.26/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, ,OASE)*sections 3.1, 3.2, 3.3, 3.4 are final*

alternative proof example 3.14 (section 3.2)

slides section 3.3

slides section 3.49/12 (7+8)

(instruction)exercises 3.3: 1, 4

exercises 3.4: 1, 2, 3additional 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.513/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.120/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, 5additional 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.210/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.113/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.417/1 (3+4)

(instruction)exercises 5.2: 1-5

additional interaction exercise

exercises 5.3: 1solutions (solutions_5.2_5.3.pdf, OASE)

interaction exercise

interaction solution20/1 (5+6)

(instruction, Q&A)

instruction, Q&A 20/1 (7+8)

19/4 | Text of resit exam (2IT71) (18-4-2017) and solution avaiable. |

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 ) |

Gerard Zwaan