Docente

Beatrice Palano


UNA VELOCISSIMA PRESENTAZIONE
DEL CORSO DI LINGUAGGI FORMALI E AUTOMI




Programma del corso di LFA

Nozioni di base.
Monoidi di parole, linguaggi, operazioni tra linguaggi, riconoscitori e generatori di linguaggi. Grammatiche e derivazioni. Grammatiche regolari, libere da contesto, dipendenti da contesto e relative classi di linguaggi.





Registro del corso di LFA
(contenuti del corso lezione per lezione)

  1. Introduzione al corso. Presentazione del programma del corso.
  2. Nozioni base della teoria dei linguaggi formali: alfabeto, monoide di parole. Linguaggio formale. Esempi di linguaggi finiti e infiniti.
  3. Operazioni su linguaggi: insiemistiche, prodotto, potenza, chiusura di Kleene. Esercizi. Codici, codici prefissi.
  4. Linguaggi e problemi di decisione. Esempi. Sistemi riconoscitivi e sistemi generativi. Procedura, algoritmo, programma.
  5. Linguaggi ricorsivi. Linguaggi ricorsivamente enumerabili. Teorema di inclusione. Esempi di linguaggi e ricorsivi. Analisi del linguaggio complemento.
  6. Esistenza di un linguaggio ricorsivamente enumerabile ma non ricorsivo. Dimostrazione.
  7. Indecidibilità del problema dell'arresto. Esistenza di un linguaggio non ricorsivamente enumerabile. Dimostrazione.
  8. Introduzione alle grammatiche. Definizioni: grammatica, derivazione, linguaggio generato. Esempi.
  9. Teorema di equivalenza tra la classe dei linguaggi generati da grammatiche e la classe dei linguaggi ricorsivamente enumerabili.
  10. Classificazione di Chomsky (versione semplificata). Esempi di grammatiche di tipo 3, 2, 1.
  11. Teorema di inclusione delle classi di linguaggi di tipo 3,2,1,0. I linguaggi di tipo 1 sono ricorsivi. Dimostrazione.
  12. Classificazione di Chomsky (versione definitiva). Forme equivalenti delle grammatiche di tipo 3.
  13. Introduzione agli automi a stati finiti. Definizione. Linguaggio riconosciuto.
  14. La relazione di indistinguibilità tra stati. Costruzione di automi a stati finiti con stati distinguibili tra loro.
  15. Sintesi di automi a stati finiti. Automa massimo e minimo. Automa minimo ottenuto dall'automa massimo senza stati indistinguibili. Dimostrazione.
  16. Algoritmo di sintesi ottima di automi a stati finiti per linguaggi regolari. Esempi. Prova di esecuzione con un linguaggio non regolare.
  17. Teorema di equivalenza tra le grammatiche di tipo 3 e gli automi a stati finiti. Automi a stati finiti non deterministici.
  18. Teorema di equivalenza tra automi a stati finiti deterministici e non deterministici. Esempi.
  19. Espressioni regolari. Teorema di Kleene. Dimostrazione dell'inclusione: ogni linguaggio denotato da espressione regolare è riconosciuto da un automa a stati finiti.
  20. Teorema di Kleene. Dimostrazione dell'inclusione: ogni linguaggio riconosciuto da un automa a stati finiti è denotato da una espressione regolare. Proprietà di chiusura dei linguaggi regolari.
  21. Grammatiche di tipo 2: alberi di derivazione e ambiguità. Forme normali di Chomsky e Greibach. Esempi.
  22. Il concetto di pila. Riconoscitori per i linguaggi liberi da contesto: automi a pila. Esempi di riconoscitori deterministici e nondeterministici.
  23. Teorema di equivalenza tra le grammatiche di tipo 2 e i riconoscitori a pila. Dimostrazione. Esempi.
  24. Il pumping lemma per i linguaggi di tipo 2. Dimostrazione. Uso del pumping lemma: esempio di applicazione su di un linguaggio di tipo 1 non di tipo 2.





Testi consigliati






Ricevimento studenti

SU APPUNTAMENTO
(da fissare via mail)

Ufficio S203

Via Comelico 39, MI






 
Avvisi per gli studenti  

Per poter sostenere l'esame di LFA è necessario iscriversi tramite Sifa.
Sono in linea gli esiti dello scritto del 26/09/2017.

Il giorno 09/10/2017 alle 10:30 sarà possibile visionare i compiti scritti
nell'ufficio della docente (II piano, stanza S203, via Comelico).








Orario delle lezioni 2017
Giorno
Ore
Aula
martedì
10:30-12:30
Aula V3
(Via Celoria 26, Settore Didattico)
giovedì
11:30-13:30
Aula Beta
(Via Comelico 39)







 
Modalità d'esame  

L'esame di LFA consiste in una prova scritta e un'eventuale prova orale. L'orale sarà richiesto a discrezione del docente. Allo scritto, oltre agli esercizi, potranno esserci domande aperte di teoria. Sia allo scritto che all'eventuale orale è previsto il salto d'appello in caso di insufficienza grave.

Nota bene: queste modalità d'esame valgono anche per gli studenti dei vecchi anni accademici (ovvero studenti non iscritti al primo anno).








Appelli esame 2017
Giorno
Esiti
23 gennaio
Esiti
13 febbraio
Esiti
14 giugno
Esiti
3 luglio
Esiti
17 luglio
Esiti
26 settembre
Esiti




Alcuni testi d'esame
Data
Testo
17/06/15
Testo
02/07/15
Testo
17/07/15
Testo
14/09/15
Testo