Automata and Formal Languages
A.Y. 2020/2021
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
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Didactic methods:
Synchronous lectures (video-lectures) will be carried out using the Zoom platform, with full lecture recording. Lectures will then be made available to allow them to be used asynchronously for students not present in the classroom.
Il programma e il materiale di riferimento compresa la modalità di verifica dell'apprendimento non subiranno variazioni.
The program and the reference material including the learning verification method will not change.
Synchronous lectures (video-lectures) will be carried out using the Zoom platform, with full lecture recording. Lectures will then be made available to allow them to be used asynchronously for students not present in the classroom.
Il programma e il materiale di riferimento compresa la modalità di verifica dell'apprendimento non subiranno variazioni.
The program and the reference material including the learning verification method will not change.
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.
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.
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 which are download from the web site of the course.
- Bertoni, Palano. Linguaggi Formali e Automi. Book note which are download from the web site of the course.
Assessment methods and Criteria
The exam consists of a written paper of about five 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 understanding of the subject and the ability to apply the theorems. In the evaluation, expressed in thirtieths, the ability to formalize the concepts is strongly considered.
Professor(s)