Linguaggi Formali e Automi

Anno Accademico 2010/2011

Edizione 1

Docente: Giovanni Pighizzini

Avvisi
Informazioni generali
Materiale di riferimento
Argomenti delle lezioni svolte

Informazioni generali

• Orari e aule
  Le lezioni si tengono nei seguenti orari:
  
  • Martedì 8.30-10.30: aula V2, Didatteca, via Venezian
    
  • Giovedì 8.30-10.30: aula V2, Didatteca, via Venezian
    
  
  
• Ricevimento studenti
  Il docente riceve gli studenti il martedì dalle 11 alle 13 (via Comelico 39, primo piano, per tale orario non è necessario fissare un appuntamento). Eventuali sospensioni o spostamenti del ricevimento vengono comunicati tramite avviso sul sito del Coordinamento Didattico di Scienze e Tecnologie Informatiche.
  Per ricevimento in altri orari è necessario inviare una email per chiedere un appuntamento.

• Date appelli d'esame
  Gli appelli d'esame sono previsti nelle seguenti date: 22 giugno, 6 luglio, 21 luglio, 26 settembre 2011. Sarà fissata un'ulteriore data nel mese di gennaio 2012. Le date indicano l'inizio dell'appello d'esame e potrebbero essere modificate di qualche giorno. Nel caso di un elevato numero di iscritti, gli stessi saranno suddivisi su più giorni.
  Si ricorda che per partecipare all'esame è necessario iscriversi tramite il servizio SIFA.

Materiale di riferimento

Testo consigliato:

• J.E. Hocroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Pearson Education, 2009.
  Indice e argomenti trattati

Argomenti delle lezioni svolte

• 15 marzo 2011 - Lezione 1
  Introduzione. Generalità su linguaggi, linguaggi formali, macchine e automi. Alcuni esempi informali di automi a stati finiti.

• 22 marzo 2011 - Lezione 2
  Nozioni base su alfabeti, stringhe, linguaggi. Il problema della rappresentazione finita di linguaggi. Il linguaggio delle parentesi bilanciate: definizione riconoscitiva e definizione generativa.

• 24 marzo 2011 - Lezione 3
  Automi a stati finiti deterministici: definizione, funzione di transizione estesa alle stringhe, linguaggio accettato. Rappresentazione mediante tabelle e mediante diagrammi di transizione. Esempi.

• 29 marzo 2011 - Lezione 4
  Automi a stati finiti nondeterministici: definizione, funzione di transizione estesa alle stringhe, linguaggio accettato. Esempi. Trasformazione di automi nondeterministici in automi deterministici: la costruzione per sottoinsiemi.

• 31 marzo 2011 - Lezione 5
  Equivalenza tra automi a stati finiti deterministici e nondeterministici. Automi con epsilon-mosse. Trasformazione di automi con epsilon-mosse in automi nondeterministici e deterministici.

• 5 aprile 2011 - Lezione 6
  Operazioni su linguaggi: operazioni insiemistiche (unione, intersezione, complemento, differenza), prodotto o concatenazione, potenza, chiusura di Kleene, chiusura positiva. Le espressioni regolari. Esempi.

• 7 aprile 2011 - Lezione 7
  La classe dei linguaggi regolari. Il teorema di Kleene (prima parte): dalle espressioni regolari agli automi a stati finiti. Esempi.

• 12 aprile 2011 - Lezione 8
  Il teorema di Kleene (seconda parte): dagli automi a stati finite alle espressioni regolari. Esempi.

• 14 aprile 2011 - Lezione 9
  Il pumping lemma per i linguaggi regolari. Esempi di dimostrazioni di non regolarità mediante il pumping lemma.

• 19 aprile 2011 - Lezione 10
  Chiusura della classe dei linguaggi regolari rispetto alle operazioni booleane. Problemi di decisione per linguaggi regolari: come decidere se un linguaggio è vuoto, finito o infinito; come decidere l'equivalenza di automi a stati finiti o di espressioni regolari.

• 28 aprile 2011 - Lezione 11
  Equivalenza e distinguibilità di stati. Minimizzazione di automi deterministici.

• 3 maggio 2011 - Lezione 12
  Automi a pila: introduzione e definizione. Configurazioni o descrizioni istantanee. Accettazione per stato finale. Accettazione per pila vuota. Simulazione di automi a pila che accettano per stati finali mediante automi a pila che accettano per pila vuota.

• 5 maggio 2011 - Lezione 13
  Simulazione di automi a pila che accettano per pila vuota mediante automi a pila che accettano per stati finali. Automi a pila deterministici. Determinismo e nondeterminismo: esempi di linguaggi riconosciuti da automi a pila nondeterministici ma non riconoscibili da automi a pila deterministici.
  Grammatiche: definizione di grammatica. Esempi.

• 10 maggio 2011 - Lezione 14
  Grammatiche: derivazioni e linguaggi. Classificazione di Chomsky delle grammatiche e dei linguaggi. Cenni all'equivalenza tra grammatiche di tipo 3 e automi a stati finiti. Grammatiche e linguaggi context-free: alberi sintattici e derivazioni a sinistra. Ambiguità e ambiguità inerente.

• 12 maggio 2011 - Lezione 15
  Equivalenza tra automi a pila e grammatiche libere dal contesto. Forme normali di Chomsky e di Greibach. Esempi.

• 17 maggio 2011 - Lezione 16
  Il pumping lemma per il linguaggi context-free. Esempi di uso del pumping lemma. Chiusura della classe deil linguaggi context-free rispetto all'unione. Non chiusura rispetto a intersezione e complemento.

• 24 maggio 2011 - Lezione 17
  Il pumping lemma per il linguaggi context-free: revisione ed esempi. Proprietà di chiusura della classe dei linguaggi context-free: chiusura rispetto a unione, intersezione e chiusura di Kleene. Chiusura rispetto all'intersezione con linguaggi regolari. Appartenenza di una stringa a un linguaggio context-free (inizio).

• 26 maggio 2011 - Lezione 18
  Appartenenza di una stringa a un linguaggio context-free: l'algoritmo CYK. Problemi di decisione per linguaggi regolari: come decidere se un linguaggio è vuoto, finito o infinito. Cenni ad alcune prorietà non decidibili.
  Codifica di stringhe mediante interi. Dimostrazioni per diagonalizzazione.

• 31 maggio 2011 - Lezione 19
  Insiemi ricorsivi e ricorsivamente numerabili. Cenni alla ricorsività dei linguaggi context-sensitive e all'equivalenza tra linguaggi di tipo 0 e linguaggi ricorsivamente numerabili. Il problema dell'arresto. Il complemento di insiemi ricorsivamente numerabili.