Course of Automi, Linguaggi e Traduttori 

Academic Year 2010-2011
(Face-to-face Course and On-line Course)

Laurea Triennale in Ingegneria Informatica

Link to: Automi, Linguaggi e Traduttori: On-line Course. (New site) (Old site)

Teacher: Alberto Pettorossi. You can talk to the teacher after the lectures or
by appointment.

Curriculum Vitae of Alberto Pettorossi.

You can send email messages to the teacher pettorossi@info.uniroma2.it

In your message, please, use the subject:

alt2011_Lastname_Firstname_EnrolmentNumber

or if you are an ‘online’ student:

alt2011online_Lastname_Firstname_EnrolmentNumber

(The word ‘EnrolmentNumber’ stands for the Italian word ‘Matricola’).

Lectures:  from 27.09.10 to 29.01.11 (No lectures from 22.12.10 to 06.01.11 inclusive) 
Monday 16:00-16:45  Room 03 n.e.
Wednesday 14:00-15:45  Room 03 n.e.

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

Tuesday 08.02.11  15:00 Room 06 n.e. The ‘Before-the-Exam’ Seminar

(1) Thursday 10.02.11  15:00 Room 03 n.e. Exam (written part) for the first and the second call

(2) Thursday 17.02.11  15:00 Room 04 n.e. Second call (oral part)

Thursday 30.06.11  16:00 Room 11 n.e. The ‘Before-the-Exam’ Seminar

(1) Tuesday 05.07.11  09:30 Room 12 n.e. Exam (written part) for the first and the second call

(2) Wednesday 13.07.11  15:00 Room 08 n.e. Second call (oral part)

Tuesday 06.09.11  16:00 Room 12 n.e. The ‘Before-the-Exam’ Seminar

(1) Thursday 08.09.11  15:00 Room 03 n.e. Exam (written part) for the first and the second call

(2) Thursday 15.09.11  15:00 Room 03 n.e. Second call (oral part)

Thursday 02.02.12  11:45 Room B15 The ‘Before-the-Exam’ Seminar

(1) Monday 13.02.12  15:00 Room C11 Exam (written part) for the first and the second call

(2) Tuesday 21.02.12 15:00 Room C12 Second call (oral part)

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

---------------------------------
*** BOOKING FOR THE FIRST CALL (1) AND THE SECOND CALL (2).
Both for the first and the second call, within four days before the date (1)
you should register using the online system http://delphi.uniroma2.it
--> You cannot register for both calls.
--> If you are an ‘online’ student, write ’online’ besides your name, please.

*** HANDING-IN YOUR HOMEWORK.
Within four days before date (1) for the first call, and date (2) for the
second call, please send to:
alt@iasi.cnr.it and pettorossi@info.uniroma2.it
a message with subject:
alt2011_Lastname_Firstname_EnrolmentNumber
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:
alt2011_Lastname_Firstname_EnrolmentNumber_CYKParser1
alt2011_Lastname_Firstname_EnrolmentNumber_LR1Parser2
If you are an ‘online’ student the names of the files should be:
altonline2011_Lastname_Firstname_EnrolmentNumber_CYKParser1
altonline2011_Lastname_Firstname_EnrolmentNumber_LR1Parser2

Do not add screenshots and strictly follows the above instruction, please.
Send 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.
---------------------------------
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
languages.

Syllabus.
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.

Homework: to be done by yourself.

Detailed syllabus and exam questions.

Previous Exam Questions.

Handouts:
1. Quantifiers.pdf

2. DistributedTermination.pdf (facoltativo)

3. HsiangTheoremProver.pdf (facoltativo)

4. LeftLinear-RightLinear-Grammars-Conversion.pdf

5. ContextFreeOnSingletonSigma.pdf (facoltativo)

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. 

Attendance 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’).

Statistics of the outcome of previous exam sessions.

Audio Recording of the lectures is available on demand (for personal use only).
------------------------------------------------------------------------------------------------------------
Suggested Textbooks.
1. A. Pettorossi: Automata Theory and Formal Languages. Second Edition. Aracne, 2009.
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 the proofs of the theorems of Chapters 4 and 5, and of Section 6.1.
2. A. Pettorossi: Techniques for Searching, Parsing, and Matching. Second Edition. Aracne, 2009.
Chapter 2.2, 2.3, 4.1, 4.2, 5, 6.1, 6.2.1, 9.1.
Errata Corrige of Books
------------------------------------------------------------------------------------------------------------
Among the many textbooks which are available for further reading on the subjects of
the course, 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,
and 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 and M. Proietti: First Order Predicate Calculus and Logic Programming. Second Edition.
Aracne, 2005.
------------------------------------------------------------------------------------------------------------