Università degli Studi di Roma "Tor Vergata"

Introduzione ai linguaggi formali e agli automi con particolare referimento
ai linguaggi regolari, ai linguaggi context-free, agli automi finiti e
agli automi pushdown. Introduzione alla teoria della computazione.
Introduzione alle techniche di base per il parsing e la compilazione
dei linguaggi di programmazione.
Con riferimento alle linee guida riportate nel documento: “ACM/IEEE-CS- Computer
Science Curricula 2013)” (www.acm.org/education/CS2013-final-report.pdf),
il corso contribuisce a coprire, tra altri, anche i seguenti argomenti
e obiettivi didattici:
- AL (Algorithmic Strategies): backtracking ricorsivo;
- AL (Fundamental Data Structures and Algorithms): algoritmo di cammino minimo e
minimo spanning tree;
- AL (Basic Automata Computability and Complexity): automi a stati finiti; espressioni
regolari; l'halting problem; grammatiche context-free;
- AL (Advanced Automata Theory and Computability): insiemi e languaggi; languaggi
regolari; rivisitazione degli automi finiti deterministici e nondeterministici e
la loro equivalenza; rivisitazione delle espressioni regulari; loro equivalenza
con gli automi finiti; proprietà di chiusura; prova di non-regolarità dei linguaggi
via il pumping lemma; languaggi context-free; automi push-down (PDAs); relazione
tra i PDAs e le grammatiche context-free; proprietà dei languaggi context-free;
macchine di Turing; macchine di Turing nondeterministiche; gerarchia di Chomsky;
la tesi di Church-Turing; Computabilità;
- IS (Natural Language Processing): algoritmi di parsing; parsing per grammatiche
context-free;
- AL (Fundamental Data Structures and Algorithms): algoritmi di pattern matching.