FORMAL LANGUAGES
Academic Year 2023/2024 - Teacher: Maria Serafina MADONIAExpected Learning Outcomes
- Knowledge and understanding: students will acquire advanced knowledge relative to the formal languages theory, with respect to possible applications too. These acquirements will help students in understanding notions, results and concepts that are fundamental for a computer scientist.
- Applying knowledge and understanding: students will develop their ability in abstraction and formalization and will acquire the expertnesses required to bite on, in a rigorous way, many applicative problems. These problems are related, for example, to the recognition of natural and artificial languages, to the string pattern matching (with important applications in bioinformatics) and to game theory.
- Making judgements: students will be able to use the appropriate formal means in different applicative contexts, motivating their choices and autonomously developing solutions.
- Communication skills: students will acquire more communication abilities and more control in the expressive and explanatory tools of the formal reasoning.
- Learning skills: students will acquire the necessary, and mainly theoretical, methodologies, to afford and solve, independently, new problems in the computer science context.
Course Structure
Classroom lessons.
Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Required Prerequisites
Attendance of Lessons
Attending lessons is not mandatory but, for a full understanding of the course topics, it is strongly recommended.
Detailed Course Content
Introduction to formal languages:
Grammars and recognizers.
Finite state automata and regular languages:
Finite state automata: deterministic, nondeterministic, with epsilon-transitions.
The class of AF-regular languages.
Regular expressions and regular languages.
Kleene's theorem.
Pumping lemma for regular languages.
Pumping Lemma and decidability algorithms for regular languages.
Myhill-Nerode's theorem.
Context-free grammars:
Parse trees.
Simplification of context-free grammars: useless symbols; epsilon-productions; unit-productions.
Chomsky Normal Form.
Greibach Normal Form.
Ambiguous, non-ambiguous and inherently ambiguous grammars.
Pumping Lemma for context-free languages.
Ogden's Lemma.
Membership problem for context-free languages.
Pushdown Automata:
Acceptance by final state and by empty stack.
Deterministic pushdown automata.
Pushdown automata and context-free grammars.
Turing Machines:
Recursively enumerable languages.
Deterministic e non-deterministic Turing Machines.
Turing Machines and unrestricted grammars.
Linear-bounded automata and context-sensitive languages:
Definition and examples.
Linear-bounded automata and context-sensitive grammars.
Chomsky Hierarchy
Textbook Information
1) John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | Introduzione ai linguaggi formali | Textbook 1) and 2) |
| 2 | Automi a stati finiti e linguaggi regolari | Textbook 1) and 2) |
| 3 | Grammatiche e linguaggi context-free | Textbook 1) and 2) |
| 4 | Automi a pila | Textbook 1) and 2) |
| 5 | Macchine di Turing | Textbook 1) and 2) |
| 6 | Automi linear-bounded e linguaggi context-sensitive | Dai testi 1) e 2) |
| 7 | Gerarchia di Chomsky | Dai testi 1) e 2) |
Learning Assessment
Learning Assessment Procedures
Written exam and oral interview.
Some ongoing tests are scheduled during the course.
It is possible to agree with the teacher the date and time for taking the exams.
Note. Verification of learning can also be carried out electronically, should conditions require it.