1. Home
  2. Education
  3. Degree programme courses
  4. Automata and Formal Languages

Automata and Formal Languages

A.Y. 2024/2025
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
The aim of the course is introducing concepts in formal language and automata theory, which play a central role in several trends in computer science, helping the student to adopt formal approaches.
Expected learning outcomes
The student should be able to manage basics on computability theory. He should be able to distinguish among several types of formal grammars, relating them with several presented computational models. He should be able to design pushdown and finite state automata for simple languages, minimize finite state automata and devise equivalent regular expressions.

Lesson period: Second semester

Lessons timetable

Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi

Exams calendar

Single course

This course can be attended as a single course.

Take a single course
Course syllabus and organization

Single session

Responsible
Palano Beatrice Santa
Lesson period
Second semester
Course syllabus
Basic notions.
Word monoids, languages, language operations, recognition and generative systems for languages. Recursive and recursively enumerable languages. Grammars and derivations. Regular, context-free, context-sensitive grammars and related classes of languages.
Regular languages.
Deterministic and non deterministic finite state automata. Regular grammars and finite state automata. Regular expressions. Kleene's Theorem. Syntactic congruences and constructions of minimal automata. Applications: regular expressions in Unix.
Context-free languages.
Derivation trees. Ambiguous grammar and languages. Chomsky normal form. Pumping lemma for context-free languages. Greibach normal form. Pushdown automata. Context-free languages and pushdown automata. Applications: XML.
Prerequisites for admission
No particular prerequisite.
Teaching methods
The teaching consists of lectures aimed at explaining the theory and performing exercises. Attending lectures is strongly encouraged.
Teaching Resources
-J.E. Hopcroft, J.D. Ullman. Introduction to automata theory, languages and computation.Addison-Wesley, 1979.
- Bertoni, Palano. Linguaggi Formali e Automi. Book note.
The course material can be found on the teaching website:
https://myariel.unimi.it/course/view.php?id=3175
Assessment methods and Criteria
The exam consists of a written paper of about three questions/exercises covering the topics of the course. The questions consist of: formal definitions, statements of theorems and algorithms of constructions/proofs. The exercises verify the applicative aspects, while open questions test the reasoning ability on the subject. The exam time is about one hour and half, and the evaluation is expressed in thirtieths. In the evaluation the ability to formalize the concepts is strongly considered. An evaluation between 18 and 24 witnesses an adeguate knowledge to present topics by using a suitable formalism. An evaluation between 25 and 30 highlights also the ability of proving/applying theorems. The evaluation is sent directly to the student via SIFA system.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Palano Beatrice Santa
Shifts:
Turno
Professor: Palano Beatrice Santa
Educational website(s)
Linguaggi formali e automi (a.a. 2024/25)
Professor(s)
Palano Beatrice Santa
Web site
Reception:
by appointment
Via Celoria, 18 - Room: 4011