Materia:Linguaggi formali e automi
Questa materia non ha ancora una introduzione.
Obiettivi
Il corso fornisce una presentazione teorica dei linguaggi formali e dei metodi per riconoscerli, generarli ed elaborarli.
Si vorrebbe creare un corso che vada crescendo nelle conoscenze dello studente in maniera graduale, arrivando a spiegare i concetti formali come una conseguenza logica dello scibile. Alcune notazioni iniziali, potranno sembrare non corrette fino all'enunciato formale.
Area di riferimento
Area di Scienze matematiche, fisiche e naturali
Corsi
Questa materia fa parte dei seguenti corsi:
Corso di Informatica
Corso di Ingegneria informatica
Dipartimento
Questa materia è curata dagli utenti del
Dipartimento: Tecnologie dell'informazione
- Rudimenti di insiemistica e logica matematica.
- Informatica teorica: si attende che lo studente sia in grado di riconoscere la tipologia di un linguaggio, sappia costruire un semplice automa che lo genera a partire da una grammatica data e viceversa.
Automi
(Questi argomenti sono in ripasso da informatica teorica)
- Automa a stati finiti deterministico
- Automa a pila
- Macchina di Turing
- Automa non deterministico
- Introduzione alle reti di Petri
- Pumping lemma
Grammatiche
(Questi argomenti sono in ripasso da informatica teorica)
Linguaggi formali
- Linguaggio
- Introduzione ai linguaggi formali
- Operazioni sui linguaggi formali
- Alberi di derivazione
- Linguaggi ed espressioni regolari
- Linguaggi liberi dal contesto (context-free)
- (wikipedia) Linguaggio di Dyck
- Automi riconoscitori ed espressioni regolari
- Grammatiche ambigue
- Grammatiche: equivalenze, forme normali e trasformazioni
- Analisi sintattica
- Traduzioni sintattiche
- Grammatica ad attributi
- Analisi statica
È possibile, e fortemente consigliato, integrare le lezioni e valutare la propria preparazione attraverso queste esercitazioni. È possibile verificare la conoscenza di un argomento specifico o dell'intero programma.
Questa materia al momento non prevede verifiche d'apprendimento.
La Biblioteca del Dipartimento di Informatica contiene risorse utili per approfondire.
Se vuoi, aggiungi tu altre risorse.In italiano
Internazionali
- (EN) Il wikilibro di valepert in inglese
- (EN) Stefano Crespi Reghizzi, Formal Languages and Compilation, Springer, 2009, ISBN 978-1-84882-049-4.