LIACS > Marcello M. Bonsangue > Fundamentele Informatica 2
Lecturer Marcello Bonsangue
Keyvan Azadbakht
Assistants Stef van Dijk,
Diederick Vermetten , and 
Joos van Zweeden
ECTS 6
Course number
4032FUIN6
Prerequisites Fundamentele Informatica 1
Language English
Examinations
(4032FUIN6T)
4 Jan 2019, 10:00-13:00 rooms Snellius B01, B02, B03
15 Mrt 2019 14:00-17:00
room Snellius B01, B03
Schedule Fall 2018

September 4, 11, 18, 25
October 2, 9, 16, 23, 30
November 6, 13, 20, 27
December 4

Lectures (4032FUIN6H): 13:30-15:15, room HUYGENS 204,
except
- 18 Sep
(HUYGENS 226),
- 27 Nov
(HUYGENS 226), and
- 4 Dec (GORL 01).

Practica (4032FUIN6W): 11:00-12:45 rooms Snellius 401, 402

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 push-down 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 push-down automata, because of its major role in compiler design and parsing.


Literature

John C. Martin, Introduction to Languages and the Theory of Computation, 4th Revised edition, McGraw Hill Higher Education, 2010, 576 pages (ISBN: 0071289429).

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 Non-deterministic automata (NFA) [Mar10]:3.2 3.18, 3.44


Homework 2 Solution Deadline:11 October
6a
9 Oct From RE to NFA-Lambda
[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


*=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):137-163, 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