|
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 Informatica Teorica) or by appointment.
You can send
email messages to the teacher: pettorossi@info.uniroma2.it
In your message, please, use the subject:
al2015_Lastname_Firstname_EnrolmentNumber
or if you are an ‘online’
student:
al2015online_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 03.03.15 to 28.06.15
Tuesday
09:30-11:15 Room B4.
Thursday 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
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’)
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: 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:
al2015_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:
al2015_Lastname_Firstname_EnrolmentNumber_CYKParser1
al2015_Lastname_Firstname_EnrolmentNumber_LR1Parser2
If you are an ‘online’ student the
names of the files should be:
alonline2015_Lastname_Firstname_EnrolmentNumber_CYKParser1
alonline2015_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.
------------------------------------------------------------------------------------