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

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