Automata and languages
- Overview
- Assessment methods
- Learning objectives
- Contents
- Full programme
- 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 ( oral) 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 exam is structured as follows: (part A) two questions concerning the notions presented in the course and their application; (part B) the proof of a theorem demonstrated in the course; (part C) exercises of the kind discussed during class exercises. During the oral exam will be evaluated the acquisition of an appropriate technical language.
The final grade will be determined as follows: 50% from the knowledge of definitions and examples of the concepts dealt during the course (part A); 20% from the knowledge and understanding of the theorem demonstrations; 30% 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 and formal languages and computability theory. The course focus is on modeling discrete systems and software/hardware systems using an abstract and formal approach. 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:
•possess basic notions on languages over a free monoid.
• 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;
• describe and use rewriting systems, grammars (Chomsky's hierarchy) and the corresponding classes of languages
•have a clear idea about the relations among finite state automata and Turing machines, and their relation with sequential programming
• 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;
• identify and use the notations (generators) for describing regular languages and context-free languages;
• appropriately apply recognizers and generators to study simple languages;
• demonstrate an understanding of the limitations of the various computational models;
• recognize and use the proper terminology of automata theory, formal languages and computability theory.
• Mathematical preliminaries. (4h)
Strings, languages and their finite description (2h)
• Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), Non-deterministic finite automata with ε-moves (ε-NFA) and their equivalence (12h)
• Compositionality and Kleene's theorem (4h)
• Regular languages: main properties and Pumping Lemma. (4h)
• Context-free grammars: derivations, derivation trees, ambiguous grammars. Structure of a parser (8h)
• Pushdown Automata (PDA): acceptance by final state and acceptance by empty stack (equivalence). Equivalence between context free languages and PDA. (4h)
• Context-free languages: main properties and Pumping Lemma. (4h)
• The Chomsky Hierarchy. (2h)
• Deterministic and Non-deterministic Turing Machines (4h).
• Recursively enumerable languages and undecidable problems. (4h)
Automata with product and non sequential models (4h)
Mathematical preliminaries: equivalence relations, orders, quotient, monoids. (4h)
Strings, languages and their finite description (2h)
• Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), Non-deterministic finite automata with ε-moves (ε-NFA) and their equivalence (12h)
• Compositionality and Kleene's theorem (4h)
• Regular languages: main properties and Pumping Lemma. (4h)
• Context-free grammars: derivations, derivation trees, ambiguous grammars. Structure of a parser (8h)
• Pushdown Automata (PDA): acceptance by final state and acceptance by empty stack (equivalence). Equivalence between context free languages and PDA. (4h)
• Context-free languages: main properties and Pumping Lemma. (4h)
• The Chomsky Hierarchy. (2h)
• Deterministic and Non-deterministic Turing Machines (4h).
• Recursively enumerable languages and undecidable problems. (4h)
Automata with product and non sequential models (4h)
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità, Pearson Paravia Bruno Mondadori, Terza Edizione, 2009.
A. Bertoni, B. Palano, Linguaggi formali e automi, http://bertoni.di.unimi.it/Linguaggi_e_Automi.pdf
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.
Il docente riceve su appuntamento, anche via Teams, previa richiesta via e-mail a nicoletta.sabadini@uninsubria.it. Il docente risponde solo alle e-mail firmate e provenienti dal dominio studenti.uninsubria.it.