Materia:Linguaggi formali e automi

 

Linguaggi formali e automi

Tutte le lezioni in ordine alfabetico

Aree di riferimento Area di Scienze matematiche, fisiche e naturali Area di Ingegneria

Corsi Questa materia fa parte dei seguenti corsi: Corso di Informatica Corso di Ingegneria informatica

Dipartimenti Questa materia è curata dagli utenti del Dipartimento: Tecnologie dell'informazione

Presentazione

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.

Prerequisiti

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.

Programma

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) Introduzione alle grammatiche Classificazione delle grammatiche Grammatiche e automi 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

Verifiche d'apprendimento

È 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.

Risorse

La Biblioteca del Dipartimento di Informatica contiene risorse utili per approfondire. Se vuoi, aggiungi tu altre risorse. In italiano Il wikilibro di valepert Espressioni regolari su wikibooks Internazionali (EN) Il wikilibro di valepert in inglese (EN) Stefano Crespi Reghizzi, Formal Languages and Compilation, Springer, 2009, ISBN 978-1-84882-049-4.

• Torna all'area:
  • Scienze matematiche, fisiche e naturali
  • Ingegneria
• Torna al corso:
  • Informatica
  • Ingegneria informatica
• Torna al Dipartimento di Informatica