
Schedule
Fall 2018
Lectures
(4032FUIN6H):
13:3015:15, room HUYGENS 204,
except  18 Sep (HUYGENS 226),  27 Nov (HUYGENS 226). No lecture on November 27th Practica (4032FUIN6W): 11:0012:45 rooms Snellius 401, 402. The last working class is on November 27th. 
Goal
The course gives an introduction is an introduction to the theory of computation with emphasis on the relationships between formal languages, automata and abstract models of computation.
Description
Automata theory and formal languages form the foundations of theoretical computer science, as they allow us to talk precisely about what is an algorithm or a computation.
An automaton is in fact a model of computation that can be defined mathematically. The simplest model that we will consider in this course is given by finite state automaton: a machine that is only able to keep track of its current state but it has no memory. Finite state automata specify an algorithmic procedure for recognizing whether a word is in a language. We will concentrate on the relationships between language recognized by a finite state automaton, language generated by a grammar and language described by a specification, and will obtain algorithms for translating one description of a language into another description of a different type.
Adding restricted form of memory to finite state automata increase their expressivity. We will study pushdown automata, i.e. the class of automata with an auxiliary memory organized as a stack. In particular we will concentrate on the class of languages recognized by pushdown automata, because of its major role in compiler design and parsing.
Literature
Schedule Lectures
Nun  Date  Topic  Reading  Exercises* 
1a  4 Sep  Overview and motivation  

1b  
Languages  [Mar10]:1.4  1.33, 1.36, 1.37 
1c  Deterministic Finite Automata (DFA)  [Mar10]:2.1  2.1, 2.2, 2.5  
2a  11 Sep 
Automata constructions  [Mar10]:2.2  2.10, 2.11, 2.12 
2b  
Distinguishability  [Mar10]:2.3  2.13, 2.14, 2.21 
3 
18 Sep 
Pumping lemma for Regular Languages  [Mar10]:2.4  2.22 
Homework 1  Solution  Deadline:28 September  
4a  25 Sep  Indistinguishability and DFA  [Mar10]:2.5  2.33, 2.36 
4b 

Minimal DFA  [Mar10]:2.6  2.55, 2.57 
5a  2 Oct 
Regular Expressions (RE)  [Mar10]:3.1  3.1(a,d), 3.3(a,b,c), 3.6, 3.7(k,l,m,n), 3.10 
5b  Nondeterministic automata (NFA)  [Mar10]:3.2  3.18, 3.44  
Homework 2  Solution  Deadline:11 October  
6a 
9 Oct  From RE to
NFALambda 
[Mar10]:3.4 
3.41, 3.49 
6b  From NFA\Lambda to NFA  [Mar10]:3.3  3.22(a,b,d), 3.37 

6c  From NFA to DFA  [Mar10]:3.3  3.38, 3.40 

7a 
16 Oct 
From FA to RE: The
L(i,j,k) method 
[Mar10]:3.5 
3.51 (b) 
7b 
From FA to RE: the
algebraic method 
Notes 1: sect 5 
3.51 (a) 

7c 
From FA
to From FA
to RE: the
state removal method 
Notes 2 
3.51
(c) 

Homework 3  Solution 
Deadline: 25 October 

8a  23 Oct  Context free grammars (CFG)  [Mar10]:4.1,4.2  4.1, 4.3 
9b  30 Oct 
Regular grammars
(RG) and regular language 
[Mar10]:4.3  4.26, 4.27, 4.29 
9b  Ambiguity of CFG 
[Mar10]:4.4  4.34, 4.36, 4.38 

10a  11 Nov 
Chomsky normal form  [Mar10]:4.5  4.48, 4.49 
10b  Pushdown automata (PDA)  [Mar10]:5.1  5.1, 5.3, 5.4, 5.6 

Homework 4  Solution 
Deadline: 16 November 

11a  13 Nov 
Deterministic Pushdown automata 
[Mar10]:5.2  5.10, 5.13,
5.15 
11b 
PDA accepting by
empty stack 
[Mar10]:5.4 

Homework 5  Solution  Deadline: 3 December  
12a  20 Nov  From CFG to PDA (topdown construction) 
[Mar10]:5.3  5.28b, 5.38a 
12b  From CFG to PDA (bottomup construction) 
[Mar10]:5.3  5.34a  
12c  From one statePDA to CFG  [Mar10]:5.4  5.32, 5.36 
*=Solutions of most of the exercises treated in the practicum can be found either at the end of the book [Mar10] (in bold) or here.
Bibliography
[BBCF10] Jean Berstel, Luc Boasson, Olivier Carton, and Isabelle Fagnot, Minimization of automata, arXiv:1010.5318v3 [cs.FL] 30 Dec 2010.[CZ02] J.M. Champarnaud and D. Ziadi, Canonical Derivatives, Partial Derivatives and Finite Automaton Constructions. Theoretical Computer Science 289(1):137163, Elsevier Science , 2002.
[Mar10] John C. Martin, Introduction to Languages and the Theory of Computation, 4th Revised edition, McGraw Hill Higher Education, 2010.
Exam and
Homework information
 Examination is worth 70% of the final grade (with a minimum of 5.5). The remaining 30% is from the average grade of the 4 best out of the 5 homeworks.
 Write clearly your name and student number in your homework solution.
 Return your homework solution as a single pdf file by email to stefvandijk.liacs@gmail.com.
 Name your pdf file containing the solution as HWxxNameSurname.pdf, where xx ranges from 1 to 5 and it is the number of homework.
 Solutions
sent after the deadlines are not accepted.
 Grades of the homeworks will be
published on blackboard.
Past Examinations
 January 2017 (solutions) and March 2017 (solutions)
 January 2018 (solutions) and March 2018 (solutions)
 January 2019 (solutions) and March 2019 (solutions)