Course of Automi e Linguaggi
Academic
Year 2011-2012
(Face-to-face Course
and On-line Course)
Laurea Triennale
in Ingegneria Informatica
Link to: Automi
e Linguaggi: On-line Course.
Teacher: Alberto Pettorossi (Professor). 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:
al2012_Lastname_Firstname_EnrolmentNumber
or if you are an ‘online’ student:
al2012online_Lastname_Firstname_EnrolmentNumber
(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. Valerio Senni,
research contract holder) (5 hours).
Lectures: from 05.03.12 to
30.06.12
Tuesday 09:30-11:15 Room B4.
Thursday
11:30-13:15 Room B4.
Seminars and Exams: (the
word ‘call’ stands for the Italian word ‘appello’)
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 second calls
(2) Tuesday 21.02.12 15:00 Room C12 Second call (oral part)
Thursday 05.07.12 15:00 Room B4 The
‘Before-the-Exam’ Seminar
(1) Tuesday 10.07.12 15:00 Room B4
Exam
(written part) for the first and second calls
(2) Tuesday 17.07.12 15:00 Room B4 Second call (oral
part)
Thursday
06.09.12 15:00 Room B4 The
‘Before-the-Exam’ Seminar
(1)
Tuesday 11.09.12
15:00 Room B4 Exam (written part) for the first and
second calls
(2) Tuesday 24.09.12 15:00 Room B4 Second call (oral
part)
Thursday
07.02.13 15:00 Room B1 The
‘Before-the-Exam’ Seminar
(1)
Tuesday 12.02.13
15:00 Room B1 Exam (written part) for the first and
second calls
(2) Tuesday 19.02.13 15:00 Room B6 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’ after 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:
al@iasi.cnr.it
and
pettorossi@info.uniroma2.it
a
message with subject:
al2012_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:
al2012_Lastname_Firstname_EnrolmentNumber_CYKParser1
al2012_Lastname_Firstname_EnrolmentNumber_LR1Parser2
If
you are an ‘online’ student the names of the files should be:
alonline2012_Lastname_Firstname_EnrolmentNumber_CYKParser1
alonline2012_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:
0.
ALTFirstLectures.pdf
2. HsiangTheoremProver.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. Third Edition. Aracne, 2011.
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. Third Edition. Aracne, 2011.
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.
------------------------------------------------------------------------------------------------------------