Course of Automi e
Linguaggi |
Laurea Triennale in Ingegneria Informatica
Link to: Automi e Linguaggi: On-line Course.
Teacher: Alberto
Pettorossi Curriculum Vitae
You can talk to the teacher after the lectures
(also those of Automatic Software Verification) or by appointment.
You can send email messages to the teacher: pettorossi@info.uniroma2.it
In your message, please, use the
subject:
al2017_Lastname_Firstname_EnrolmentNumber
or if you are an ‘online’
student:
al2017online_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. Xxx Yyy) (5 hours).
Lectures: from 06.03.17 to 24.06.17
Tuesday 09:30-11:15 Room B4.
Thursday 09:30-11: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
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.
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’).
Handouts:
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’)
Thursday
x1.06.17 15:00 Room B11 The ‘Before-the-Exam’ Seminar
(1) Thursday y1.06.16
15:00 Room B3 Exam (written part) for the first and
second calls
(2) Thursday
z1.07.17 15:00 Room C1 Second call
Tuesday
x2.09.16 15:00 B11 The ‘Before-the-Exam’ Seminar
(1) Thursday
y2.09.16 15:00 Room B4 Exam (written part) for the first
and
second calls
(2) Tuesday
z2.09.16 15:00 Room B4 Second call
Thursday
x3.02.17 11:45 Room B15 The ‘Before-the-Exam’ Seminar
(1) Monday
y3.02.17 15:00 Room C11 Exam (written part) for the first and
second calls
(2) Tuesday
z3.02.17 15:00 Room C12 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: http://delphi.uniroma2.it
---------------------------------
*** 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:
al2017_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:
al2017_Lastname_Firstname_EnrolmentNumber_CYKParser1
al2017_Lastname_Firstname_EnrolmentNumber_LR1Parser2
If you are an ‘online’
student the names of the files should be:
alonline2017_Lastname_Firstname_EnrolmentNumber_CYKParser1
alonline2017_Lastname_Firstname_EnrolmentNumber_LR1Parser2
Do not add screenshots and strictly follow
the above instructions, 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.
---------------------------------
Homework: to be done by yourself.
Detailed syllabus and exam questions.
Previous Exam Questions.
Statistics of the outcome of previous exam
sessions.
-------------------------------------------------------------------------------------
Textbooks
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)
-------------------------------------------------------------------------------------
Among 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,
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, M. Proietti: First Order Predicate Calculus and Logic
Programming.
Third Edition.
Aracne, 2013.
------------------------------------------------------------------------------------