1014420 - LINGUAGGI FORMALI

1. Conoscenza e capacità  di comprensione (knowledge and understanding): il corso ha come obiettivo principale l'acquisizione da parte dello studente di conoscenze avanzate di teoria dei linguaggi formali, relativamente anche a  possibili applicazioni. Si noti che  gli studi in tale ambito consentiranno allo studente  di comprendere meglio nozioni, risultati e concetti fondamentali per un informatico.
2. Capacità  di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente svilupperà le  sue capacità di formalizzazione ed astrazione  e acquisirà le competenze necessarie per affrontare in modo chiaro e rigoroso numerosi problemi di carattere applicativo. Tali problemi spaziano dal riconoscimento di linguaggi artificiali e naturali, al pattern matching di stringhe (con applicazioni importanti alla bioinformatica), alla teoria dei giochi.
3. Autonomia di giudizio (making judgements): lo studente sarà in grado di utilizzare gli strumenti formali più opportuni in diversi contesti applicativi, motivandone adeguatamente la scelta ed elaborando autonomamente proprie soluzioni.
4. Abilità comunicative (communication skills): lo studente acquisirà ulteriori abilità comunicative e una maggiore padronanza degli strumenti espressivi e argomentativi del ragionamento formale.
5. Capacità  di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente le necessarie metodologie, soprattutto teoriche, per poter affrontare e risolvere autonomamente nuove problematiche che dovessero sorgere durante l'attività progettuale tipica di un Laureato Magistrale.

Didattica frontale.

Nota. Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.

Nozioni di base di Logica e Matematica discreta.

 

La frequenza delle lezioni non è obbligatoria ma, per una piena comprensione degli argomenti del corso, è fortemente consigliata.

Introduzione ai linguaggi formali:

Grammatiche e riconoscitori.

Automi a stati finiti e linguaggi regolari:

Automi a stati finiti: deterministici, non deterministici, con epsilon-transizioni.

Equivalenza fra Automi a stati finiti con epsilon-transizioni e Automi a stati finiti senza epsilon-transizioni.

Proprieta’ di chiusura della classe dei linguaggi AF-regolari.

Espressioni regolari e linguaggi regolari.

Ogni linguaggio regolare e’ AF-regolare.

Teorema di Kleene.

Pumping lemma per linguaggi regolari (solo enunciato).

Applicazioni del Pumping Lemma: algoritmi di decidibilità per linguaggi regolari.

Teorema di Myhill-Nerode.

Minimizzazione di automi a stati finiti.

Applicazioni.

Grammatiche context-free:

Alberi di derivazione.

Semplificazione di grammatiche context-free: eliminazione dei simboli inutili; eliminazione delle epsilon-produzioni; eliminazione delle produzioni unitarie.

Forma normale di Chomsky:trasformazione di una grammatica context-free in un equivalente in CNF.

Forma normale di Greibach (solo la definizione).

Grammatiche ambigue, non-ambigue e inerentemente ambigue.

Pumping Lemma per linguaggi context-free.

Applicazioni del Pumping Lemma per linguaggi context-free.

Lemma di Ogden (solo enunciato). 

Il linguaggio L= {aⁱb^jc^k |  i ≠ j,  j ≠ k , i ≠ k}  non e’ context-free.

Problema dell’appartenenza per linguaggi context-free.

Applicazioni.

Automi a pila:

Linguaggio accettato per stack vuoto e per stati finali.

Equivalenza dei due metodi di accettazione.

Automi a pila deterministici.

Equivalenza tra automi a pila e grammatiche context-free.

Applicazioni.

Macchine di Turing:

Linguaggi ricorsivamente enumerabili.

Equivalenza fra macchine di Turing deterministiche e non deterministiche.

Equivalenza fra macchine di Turing e grammatiche senza restrizioni.

Applicazioni.

Automi linear-bounded e linguaggi context-sensitive:

Definizioni ed esempi

Equivalenza tra automi linear-bounded  e grammatiche context-sensitive.

 

Gerarchia di Chomsky

 

 

Libro di testo:

         1) John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.

 

Esame scritto e colloquio orale sugli argomenti presentati a lezione.

Durante il corso sono previste alcune prove in itinere.

È possibile concordare col docente la data e l'orario per lo svolgimento delle prove d'esame.

Per l'attribuzione del voto finale si seguiranno di norma i seguenti criteri:
- non approvato: lo studente non ha acquisito i concetti di base.
- 18-23: lo studente dimostra una padronanza minima dei concetti di base, le sue capacità di esposizione e di collegamento dei contenuti sono modeste.
- 24-27:  lo studente dimostra una buona padronanza dei contenuti del corso, le sue capacità di esposizione e di collegamento dei contenuti sono buone.
- 28-30 e lode: lo studente ha acquisito tutti i contenuti del corso ed è in grado di esporli compiutamente e di collegarli con spirito critico.

Nota. La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.

http://www.dmi.unict.it/madonia/linguaggiFormali.html