Automata and languages
- Overview
- Assessment methods
- Learning objectives
- Contents
- Bibliography
- Teaching methods
- Contacts/Info
The prerequisites for a profitable learning and for achieving the objectives of the course include the basic mathematical notions and the proof techniques imparted in the fundamental teaching of Algebra and Geometry of the first year, which is therefore a pre-requisite. Moreover, some knowledge of programming languages and algorithms and data structures will be helpful.
The exam is written and it aims to verify the acquisition and the correct understanding of the contents of the course and the ability to apply them to so solve some simple problems. The written exam is structured as follows: (part A) two questions concerning the notions presented in the course; (part B) the proof of a theorem demonstrated in the course; (part C) five exercises of the kind discussed during class exercises.
The final grade will be determined as follows: 30% from the knowledge of definitions and examples of the concepts dealt during the course and the ability to describe them with an appropriate technical language (part A); 20% from the knowledge and understanding of the theorem demonstrations; 50% from the proper conduct of the exercises.
The final grade is expressed in a score out of 30, where 18 represents the minimum and 30 the maximum.
This is a theoretical course providing an introduction to automata theory and formal languages and the main limitative results of computability theory. Such knowledge is aimed at forming and increasing the ability to manage abstraction of information through symbolic representation and thus the ability to understand an abstract and symbolic language; these aspects have a central role in several areas of computer science as compiler implementation, complex system modeling and software engineering.
Expected learning outcomes. Students will be able to.
(1) describe the basic models of computation (finite state automata, push-down automata, Turing machines) their properties and their computational power in terms of recognized languages;
(2) formally define the notion of computation in the above computational models;
(3) identify the role of the various languages (in particular regular and context-free languages) in the compilation process of programming-languages and in other basic language applications;
(4) identify and use the notations (generators) for describing regular languages and context-free languages;
(5) appropriately apply recognizers and generators to study simple languages;
(6) demonstrate an understanding of the limitations of the various computational models;
(7) recognize and use the proper terminology of automata theory, formal languages and computability theory.
• Mathematical preliminaries. (4h)
• Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA). Equivalence between DFA and NFA. (10h, goals 1,2,7)
• Non-deterministic finite automata with ε-moves (ε-NFA). Equivalence between NFA and ε-NFA. (4h, goals 1,5,6)
• Regular expressions. Equivalence between regular expressions and ε-NFA. (4h, goals 1,5)
• Regular languages: main properties and Pumping Lemma. (4h, goals 5,6)
• Context-free grammars: derivations, derivation trees, ambiguous grammars. Structure of a parser (6h, goals 3,4,5)
• Pushdown Automata (PDA): acceptance by final state and acceptance by empty stack (equivalence). Equivalence between context free languages and PDA. (4h, goals 1,3,5,7)
• Context-free languages: main properties and Pumping Lemma. (4h, goals 1,5,7)
• The Chomsky Hierarchy. (2h, goals 4,7)
• Deterministic and Non-deterministic Turing Machines (4h, goals 1,3).
• Recursively enumerable languages and undecidable problems. (6h, goals 1,6,7)
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità, Pearson Paravia Bruno Mondadori, Terza Edizione, 2009.
Slides and exercises (PDF) are available on the e-learning platform.
The teaching activities include lectures (40h) and class exercises (12h). The arguments presented during lectures are applied through class exercises; students are expected to actively participate in exercises discussion. The presented exercises have an essential role in preparing the final exam.
Office hours: by appointment via email.