Course of Automi e Linguaggi 
Academic Year 2014-2015
(Face-to-face Course and On-line Course) 

Laurea Triennale in Ingegneria Informatica 

Link to: Automi e Linguaggi: On-line Course.

Teacher: Alberto Pettorossi  Curriculum Vitae
can talk to the teacher after the lectures
those of Informatica Teorica) or by appointment.

You can send email messages to the teacher:

In your message, please, use the subject:
or if you are an ‘online’ student:
(The word ‘EnrolmentNumber’ stands for the Italian word ‘Matricola’). 

6 cfu (crediti formativi). Code: 8037602
Settore Scientifico Disciplinare: Sistemi di Elaborazione delle Informazioni.
ING-INF/05 09-H1
60 hours of face-to-face teaching (single module).
Contratto integrativo: Theory of Parsing
(Dr. Ing. Xxx Yyy) (5 hours).

 Lectures:  from 03.03.15 to 28.06.15
  09:30-11:15  Room B4.
11:30-13:15  Room B4.

  Learning Objectives.
Introduction to formal languages and automata with particular reference to
regular languages, context-free languages, finite automata, and
pushdown automata. Introduction to the theory of computation
Introduction to the basic techniques for parsing and compiling programming

Mathematical Preliminaries: relations, functions. Chomsky Hierarchy.
Regular Languages, regular expressions, deterministic and nondeterministic finite automata.
Parsing of regular languages.
Context-free languages and deterministic and nondeterministic pushdown automata.
Parsing of context-free languages: Cocke-Younger-Kasami parser, chop-expand parser,
Earley parser (optional), LL(1) parsers, LR(0) parsers, LR(1) parsers,  LALR(1) parsers.
Turing Machines and type 0 grammars and languages. Type 1 grammars and languages.
Decidable, undecidable, and semidecidable problems.
Knuth-Morris-Pratt pattern matcher. Hoare triples for partial correctness.

  Requirements for the course: Fundamentals notions of Computer Science.
Elements of C++ or Java programming. Use of arrays, lists, pointers, and recursion.
Elements of Algebra and elements of Predicate Calculus. 

to lectures is compulsory.
The exam consists in the presentation and the discussion of the homework (to be done by
him/herself), and a written and an oral session.
The student should come to the exam sessions with his/her enrolment book (‘libretto’).

0. ALFirstLectures.pdf
1. Quantifiers.pdf
2. HsiangTheoremProver.pdf (facoltativo)
3. ParsingSummaryPages.pdf

(*** information to be updated ***)

Seminars and Exams: (the word ‘call’ stands for the Italian word ‘appello’)            

       Monday     06.07.15  15:00 Room B16  The ‘Before-the-Exam’ Seminar
(1) Wednesday  08.07.15  15:00 Room B2   Exam (written part) for the first and
                                         second calls
(2) Tuesday    21.07.15  15:00 Room B16  Second call 

       Wednesday  08.09.15  15:00 Room Disegno-1  The ‘Before-the-Exam’ Seminar
(1) Tuesday    10.09.15  15:00 Room B2   Exam (written part) for the first and
                                        second calls
(2) Friday     24.09.15  15:00 Room B2   Second call

       Thursday   28.01.16  15:00 Room C10 The ‘Before-the-Exam’ Seminar
(1) Tuesday    02.02.16  15:00 Room B4 Exam (written part) for the first and
                                        second calls
(2) Thursday   25.02.16  15:00 Room Aula 2
Second call 

The dates of the oral exam for the first call will be announced at the end of the written exam.

Updated information is/will be available at:

Both for the first and the second call, within four days before the date (1)
should register using the online system
--> You cannot register for both calls.
--> If you are an ‘online’ student, write ’online’ after your name, please.

Within four days before date (1) for the first call, and date (2) for the
second call, please send to: and
a message with subject:
and body:

Invio in allegato i miei elaborati per le due prove in itinere che ho fatto da
  solo/a. Firstname Lastname

You should attach to the message two text files (with extension .cpp or .java or
.txt). These files should contain your solution to the two homework
exercises. Each program should be documented and should contain instructions for
its compilation and execution. Please, include also some execution tests as
comments to the code of each program. The names of the files should be:

If you are an ‘online’ student the names of the files should be:

Do not add screenshots and strictly follow the above instructions, please.
the message with the two attached files, according to the above
instructions, even if you have done so for a previous exam call.
Normally, you cannot register to more than three exam calls per academic year.


Homework: to be done by yourself. 

Detailed syllabus and exam questions.

Previous Exam Questions.

Statistics of the outcome of previous exam sessions.

1. A. Pettorossi:
Automata Theory and Formal Languages. Fourth Edition. Aracne, 2013.
   Without Sections 1.6, 2.7, 2.11, 3.13.2, 3.14, 3.15, 3.16, 6.2, 6.3, 6.4, 7.1,
  7.2, 7.6. and without the proofs of the theorems of Chapters
4 and 5, and of Section 6.1.
2. A. Pettorossi:
Techniques for Searching, Parsing, and Matching. Fourth Edition.
   Aracne, 2013. Chapter 2.2, 2.3, 4.1, 4.2, 5, 6.1, 6.2.1, 9.1.
Errata Corrige of Books (Please download)
the many textbooks which are available for further reading, we list the following ones:
3. A.V. Aho, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools.
   Addison-Wesley, 1986. This book is also known as "The Dragon Book".
4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction
to Automata Theory,Languages,
Computation. Addison-Wesley Pub. Co., 2001 (Revised Edition).
5. A. Pettorossi: Quaderni di Informatica Parte I. Second Edition.
Aracne, 2004.
   Chapters 1 and 8.
6. A. Pettorossi, M. Proietti:
First Order Predicate Calculus and Logic Programming.
   Third Edition. Aracne, 2013.