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.

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

• J.E. Hopcroft, J.D. Ullman. Introduction to automata theory, languages and computation.Addison-Wesley, 1979.

• A. Bertoni, B. Palano Linguaggi Formali e Automi. Dispense:
• Capitolo 1  [lfa-cap1.pdf]
• Capitolo 2  [lfa-cap2.pdf]
• Capitolo 3  [lfa-cap3.pdf]

 
 

---