Fondamenti di Informatica
A.A. 2011-2012

Argomenti delle lezioni

• Lezione del 6 marzo
  Cap. 1 - Sez. 1.1, 1.5
  Introduzione al corso: orario, programma, libri di testo e modalita' d'esame.
  Introduzione alla teoria dei linguaggi formali. Linguaggi come problemi decisionali.
  Notazioni su alfabeto, parole (stringhe). Lunghezza di una parola. Prefissi, suffissi, fattori. Linguaggi. Operazioni tra linguaggi. Esempi di linguaggi.

• Lezione del 8 marzo.
  Cap. 2 - Sez. 2.2
  Definizione informale di automa a stati finiti. Costruzione dell' automa che riconosce il linguaggio delle parole di lunghezza pari. Costruzione dell' automa che riconosce il linguaggio su Σ ={a,b}di tutte le parole che contengono abb.
  Esempio: automa che riconosce il linguaggio su Σ ={a,b}di tutte le parole che contengono un numero pari di a e un numero pari di b.
  Automi deterministici a stati finiti. Definizione formale. Funzione di transizione estesa. Definizione di linguaggio accettato. Linguaggi regolari.
  Rappresentazione di un automa tramite il grafo delle transizioni.
  
• Lezione del 13 marzo.
  Cap. 2 - Sez. 2.3
  Automi non determinisitici. Definizione ed esempi. La funzione di transizione estesa.
  Esempio: automa che riconosce il linguaggio su Σ ={a,b}di tutte le parole che terminano per aa.
  Teorema di equivalenza dei DFA e NFA. Dimostrazione. La costruzione per sottoinsiemi. Esempi. Costruzione di un automa deterministico equivalente ad uno dato non deterministico costruendo solo gli stati raggiungibili.
• Lezione del 15 marzo.
  Cap. 2 - Sez. 2.3- 2.4 (lettura)
  Un caso sfavorevole della costruzione per sottoinsiemi. Automa non-deterministico per il linguaggio delle parole in cui il quarto simbolo da destra e' una b.
  Teorema: Esiste un NFA con n+1 stati per cui ogni DFA equivalente ha almeno 2^n stati. Dimostrazione.
  Cenni su automi per ricerche testuali.
  Correzioni esercizi settimana precedente.
• Lezione del 20 marzo.
  Cap. 2 - Sez. 2.5
  Automi non deterministici con epsilon-transizioni. Definizione ed esempi. Linguaggio accettato. Epsilon-chiusura di uno stato. Esempi.
  Definizione formale dell'automa deterministico equivalente ad un dato automa con epsilon-transizioni. Esempi.
  Correzioni esercizi settimana precedente.
• Lezione del 22 marzo.
  Cap. 3 - Sez. 3.1, Sez 3.2.3. Sez. 3.4.1-3.4.5
  Definizione formale delle espressioni regolari (RE) e dei linguaggi corrispondenti. Esempi.
  Proprieta' algebriche per le espressioni regolari..
  Costruzione dell'epsilon automa corrispondente ad una data espressione regolare.
• Lezione del 27 marzo.
  Cap. 3 - Sez. 3.2
  Equivalenza dei linguaggi descritti da RE e accettati da automi finiti.
  Costruzione di una RE equivalente ad un DFA. La tecnica eliminazione degli stati.
  Esempi.
• Lezione del 29 marzo.
  Cap. 4 - Sez. 4.1 (4.1.1, 4.1.2)
  Pumping lemma per linguaggi regolari. Dimostrazione.
  Esempio di applicazione del pumping lemma per la dimostrazione che il linguaggio delle parole aⁿbⁿ non è regolare.
  Esempi vari di applicazioni del Pumping Lemma.
  

• Lezione del 5 aprile.
  Cap. 4 - Sez. 4.2 (4.2.1, 4.2.2, 4.2.3-solo enunciati)
  Esempio di applicazione del pumping lemma per la dimostrazione che il linguaggio delle parole a^p, con p numero primo, non è regolare.
  Proprietà di chiusura dei linguaggi regolari rispetto alle varie operazioni. Cenni delle dimostrazioni.
  Applicazioni delle proprieta' di chiusura per mostrare che certi linguaggi sono regolari.

• Lezione del 12 aprile.
  Cap. 4 - Sez. 4.4.1, 4.4.2
  Problemi di decidibilita' per linguaggi regolari.
  Relazione di equivalenza tra stati di un DFA. Algoritmo "riempi tabella" per individuare tutti gli stati indistinguibili di un automa.
  Equivalenza di automi.

• Lezione del 17 aprile
  Cap. 4 - Sez. 4.4.3
  Calcolo dell'automa minimale. Dimostrazione dell'unicita' dell'automa minimale. Esempio.

• Lezione del 19 aprile.  
  Cap. 5 - Sez. 5.1, 5.2.1, 5.2.2., 5.4.1
  Grammatiche context-free: definizione ed esempi. Derivazioni usando una grammatica; derivazioni sinistre e destre. Definizione di linguaggio generato da una grammatica. Esempi di grammatiche.
  Alberi di derivazione per una grammatica.Grammatiche ambigue.
• Lezione del 24 aprile.
  Cap. 6 - Sez. 6.1
  Automi a pila. Esempi e definizione formale. Descrizione istantanea di un automa a pila. Linguaggio accettato da un automa a pila. Esempi.
• Lezione del 26 aprile.
  Cap. 8 - Sez. 8.1 (lettura), 8.2
  Cenni storici sulla teoria della calcolabilita'. Definizione informale di macchina di Turing. Esempio di macchina di Turing che accetta il linguaggio delle parole aⁿbⁿ Definizione formale di macchina di Turing. Definizione formale di di configurazione istantanea e di linguaggio accettato.
• Lezione del 3 maggio.
  Cap. 8 - Sez. 8.2
  Definizione formale di di configurazione istantanea e di computazione di una macchina di Turing. Definizione di linguaggio accettato per halt o per stato finale. Linguaggi ricorsivamente enumerabili e linguaggi ricorsivi.
  Macchine di Turing che calcolano funzioni. Esempi.

• Lezione del 8 maggio.
  Cap. 8 - Sez. 8.3. , 8.4.1 - 8.4.3
  Tecniche di programmazione di macchine di Turing: la memoria nello stato, macchine multitraccia.
  Definizione di macchina di Turing multinastro. Teorema di equivalenza tra macchine di Turing standard e macchine multinastro. Dimostrazione.
• Lezione del 10 maggio.
  Cap. 8 - Sez. 8.4.4, Sez. 8-6 (lettura) Cap. 9 - Sez. 9.2.1- 9.2.2
  Definizione di Macchina di Turing non deterministica. Teorema di equivalenza tra macchine di Turing deterministiche e non deterministiche. Dimostrazione.
  Teorema: Il complementare di un linguaggio ricorsivo e' ricorsivo. Dimostrazione.
  Teorema: Se sia un linguaggio L che il suo complementare sono ricorsivamente enumerabili allora sono entrambi ricorsivi. Dimostrazione.
• Lezione del 15 maggio.
  Cap. 9 - Sez. 9.1, Cap. 9 - Sez 9.2.2.
  Enumerazione delle stringhe binarie. Codifica per le macchine di Turing. Il linguaggio diagonale. Dimostrazione che il linguaggio diagonale non e' ricorsivamente enumerabile.
• Lezione del 17 maggio.
  Cap. 9 - Sez. 9.2
  Il linguaggio universale. Dimostrazione che il linguaggio universale e' ricorsivamente enumerabile.
  Dimostrazione dell'indecidibilita' del linguaggio universale.
  Cenni su altri problemi indecidibili: problema di corrispondenza di Post e problemi di piastrellamento del piano.

---