Videolezioni, parte I: teoria dei linguaggi
Lezione 01
Lezione 01
Parte 1: Introduzione ed organizzazione del corso [1:09:15]
Parte 1: Introduzione ed organizzazione del corso [1:09:15]
lez-01-01.mp4Parte 2: Le origini dell'Informatica Teorica [24:59]
Parte 2: Le origini dell'Informatica Teorica [24:59]
lez-01-02.mp4Parte 3: Esempio di un programma a stati finiti [15:55]
Parte 3: Esempio di un programma a stati finiti [15:55]
lez-01-03.mp4Lezione 02
Lezione 02
Parte 1: Stringhe e linguaggi [13:38]
Parte 1: Stringhe e linguaggi [13:38]
lez-02-01.mp4Parte 2: Automi a stati finiti deterministici (DFA) [24:22]
Parte 2: Automi a stati finiti deterministici (DFA) [24:22]
lez-02-02.mp4Parte 3: Linguaggi regolari e loro chiusura rispetto ad unione ed intersezione [26:25]
Parte 3: Linguaggi regolari e loro chiusura rispetto ad unione ed intersezione [26:25]
lez-02-03.mp4Parte 4: Automi a stati finiti non deterministici [24:49]
Parte 4: Automi a stati finiti non deterministici [24:49]
lez-02-04.mp4Lezione 03
Lezione 03
Parte 1: Equivalenza di DFA e NFA [15:33]
Parte 1: Equivalenza di DFA e NFA [15:33]
lez-03-01.mp4Parte 2: Esercizio: derivazione di un DFA equivalente ad un NFA [16:18]
Parte 2: Esercizio: derivazione di un DFA equivalente ad un NFA [16:18]
lez-03-02.mp4Parte 3: Dimostrazioni di chiusura dei linguaggi regolari con NFA [15:41]
Parte 3: Dimostrazioni di chiusura dei linguaggi regolari con NFA [15:41]
lez-03-03.mp4Parte 4: Espressioni regolari (REX) [15:46]
Parte 4: Espressioni regolari (REX) [15:46]
lez-03-04.mp4Parte 5: Le espressioni regolari generano linguaggi regolari [12:52]
Parte 5: Le espressioni regolari generano linguaggi regolari [12:52]
lez-03-05.mp4Parte 6: Esercizi: costruzione di automi corrispondenti a espressioni regolari [14:51]
Parte 6: Esercizi: costruzione di automi corrispondenti a espressioni regolari [14:51]
lez-03-06.mp4Lezione 04
Lezione 04
Parte 1: Automi a stati finiti non deterministici generalizzati (GNFA) [18:23]
Parte 1: Automi a stati finiti non deterministici generalizzati (GNFA) [18:23]
lez-04-01.mp4Parte 2: Conversione da GNFA ad espressione regolare [18:53]
Parte 2: Conversione da GNFA ad espressione regolare [18:53]
lez-04-02.mp4Parte 3: Esercizio: conversione da DFA ad espressione regolare [20:35]
Parte 3: Esercizio: conversione da DFA ad espressione regolare [20:35]
lez-04-03.mp4Parte 4: Il "pumping lemma" per i linguaggi regolari (enunciato) [19:01]
Parte 4: Il "pumping lemma" per i linguaggi regolari (enunciato) [19:01]
lez-04-04.mp4Parte 5: Il "pumping lemma" per i linguaggi regolari (dimostrazione) [18:18]
Parte 5: Il "pumping lemma" per i linguaggi regolari (dimostrazione) [18:18]
lez-04-05.mp4Lezione 05
Lezione 05
Parte 1: Applicazione del pumping lemma [18:02]
Parte 1: Applicazione del pumping lemma [18:02]
lez-05-01.mp4Parte 2: Esercizi: dimostrare non regolaritĂ usando il pumping lemma [17:07]
Parte 2: Esercizi: dimostrare non regolaritĂ usando il pumping lemma [17:07]
lez-05-02.mp4Parte 3: Esercizi: altre applicazioni del pumping lemma [13:01]
Parte 3: Esercizi: altre applicazioni del pumping lemma [13:01]
lez-05-03.mp4 Parte 4: Chiusura dei linguaggi regolari rispetto a complemento e inverso [18:14]
Parte 4: Chiusura dei linguaggi regolari rispetto a complemento e inverso [18:14]
lez-05-04.mp4 Parte 5: Chiusura dei linguaggi regolari rispetto all'omomorfismo [18:02]
Parte 5: Chiusura dei linguaggi regolari rispetto all'omomorfismo [18:02]
lez-05-05.mp4Parte 6: Introduzione alle grammatiche libere dal contesto (CFG) [10:55]
Parte 6: Introduzione alle grammatiche libere dal contesto (CFG) [10:55]
lez-05-06.mp4Lezione 06
Lezione 06
Parte 1: Linguaggi liberi dal contesto (CFL) [19:25]
Parte 1: Linguaggi liberi dal contesto (CFL) [19:25]
lez-06-01.mp4Parte 2: Chiusura dei CFL rispetto all'unione. Alberi sintattici [20:39]
Parte 2: Chiusura dei CFL rispetto all'unione. Alberi sintattici [20:39]
lez-06-02.mp4Parte 3: AmbiguitĂ di CFG e CFL. Forma normale di Chomsky [18:07]
Parte 3: AmbiguitĂ di CFG e CFL. Forma normale di Chomsky [18:07]
lez-06-03.mp4Parte 4: Esercizio: conversione di una grammatica in forma normale di Chomsky [15:03]
Parte 4: Esercizio: conversione di una grammatica in forma normale di Chomsky [15:03]
lez-06-04.mp4Parte 5: Automi a pila (PDA) [18:20]
Parte 5: Automi a pila (PDA) [18:20]
lez-06-05.mp4Lezione 07
Lezione 07
Parte 1: Esercizio: costruzione di un PDA che riconosce un CFL [20:47]
Parte 1: Esercizio: costruzione di un PDA che riconosce un CFL [20:47]
lez-07-01.mp4Parte 2: Esercizi: ulteriori esempi di PDA [14:48]
Parte 2: Esercizi: ulteriori esempi di PDA [14:48]
lez-07-02.mp4Parte 3: Equivalenza tra CFG e PDA: costruzione del PDA per una generica CFG [22:20]
Parte 3: Equivalenza tra CFG e PDA: costruzione del PDA per una generica CFG [22:20]
lez-07-03.mp4Parte 4: Equivalenza tra CFG e PDA: costruzione di una CFG per un generico PDA (idea) [26:22]
Parte 4: Equivalenza tra CFG e PDA: costruzione di una CFG per un generico PDA (idea) [26:22]
lez-07-04.mp4Parte 5: Equivalenza tra CFG e PDA: costruzione di una CFG per un generico PDA (dimostr.) [19:37]
Parte 5: Equivalenza tra CFG e PDA: costruzione di una CFG per un generico PDA (dimostr.) [19:37]
lez-07-05.mp4Lezione 08
Lezione 08
Parte 1: Il "pumping lemma" per i linguaggi liberi dal contesto (enunciato) [13:49]
Parte 1: Il "pumping lemma" per i linguaggi liberi dal contesto (enunciato) [13:49]
lez-08-01.mp4Parte 2: Il "pumping lemma" per i linguaggi liberi dal contesto (dimostrazione) [13:30]
Parte 2: Il "pumping lemma" per i linguaggi liberi dal contesto (dimostrazione) [13:30]
lez-08-02.mp4Parte 3: Esercizi: applicazioni del pumping lemma per CFL [16:34]
Parte 3: Esercizi: applicazioni del pumping lemma per CFL [16:34]
lez-08-03.mp4Parte 4: ProprietĂ di chiusura di CFL rispetto a vari operatori [11:53]
Parte 4: ProprietĂ di chiusura di CFL rispetto a vari operatori [11:53]
lez-08-04.mp4Parte 5: Automi a pila deterministici (DPDA) e linguaggi CFL deterministici (DCFL) [20:08]
Parte 5: Automi a pila deterministici (DPDA) e linguaggi CFL deterministici (DCFL) [20:08]
lez-08-05.mp4Parte 6: ProprietĂ di chiusura di DCFL rispetto a diversi operatori [18:05]
Parte 6: ProprietĂ di chiusura di DCFL rispetto a diversi operatori [18:05]
lez-08-06.mp4Lezione 09
Lezione 09
Parte 1: Linguaggi liberi dal contesto con marcatore di fine stringa [12:44]
Parte 1: Linguaggi liberi dal contesto con marcatore di fine stringa [12:44]
lez-09-01.mp4Parte 2: Linguaggi liberi dal contesto con marcatore di fine stringa (cont.) [21:53]
Parte 2: Linguaggi liberi dal contesto con marcatore di fine stringa (cont.) [21:53]
lez-09-02.mp4Parte 3: Riduzioni e maniglie per le grammatiche libere dal contesto [18:23]
Parte 3: Riduzioni e maniglie per le grammatiche libere dal contesto [18:23]
lez-09-03.mp4Parte 4: Definizione delle grammatiche libere dal contesto deterministiche (DCFG) [18:14]
Parte 4: Definizione delle grammatiche libere dal contesto deterministiche (DCFG) [18:14]
lez-09-04.mp4Parte 5: Il test DK: costruzione degli automi K e DK [21:36]
Parte 5: Il test DK: costruzione degli automi K e DK [21:36]
lez-09-05.mp4Parte 6: Esempio di costruzione dell'automa K [11:12]
Parte 6: Esempio di costruzione dell'automa K [11:12]
lez-09-06.mp4Lezione 10
Lezione 10
Parte 1: Esempio di costruzione dell'automa DK [14:31]
Parte 1: Esempio di costruzione dell'automa DK [14:31]
lez-10-01.mp4Parte 2: Il funzionamento del test DK [13:11]
Parte 2: Il funzionamento del test DK [13:11]
lez-10-02.mp4Parte 3: Esercizi sul test DK [14:15]
Parte 3: Esercizi sul test DK [14:15]
lez-10-03.mp4Parte 4: Per ogni grammatica DCFG esiste un automa a pila deterministico equivalente [24:28]
Parte 4: Per ogni grammatica DCFG esiste un automa a pila deterministico equivalente [24:28]
lez-10-04.mp4Parte 5: Per ogni DPDA che riconosce un linguaggio marcato esiste una DCFG equivalente [18:45]
Parte 5: Per ogni DPDA che riconosce un linguaggio marcato esiste una DCFG equivalente [18:45]
lez-10-05.mp4Parte 6: La classe dei linguaggi generati da grammatiche libere dal contesto deterministiche [11:15]
Parte 6: La classe dei linguaggi generati da grammatiche libere dal contesto deterministiche [11:15]
lez-10-06.mp4Lezione 11
Lezione 11
Parte 1: Le grammatiche LR(k) [13:05]
Parte 1: Le grammatiche LR(k) [13:05]
lez-11-01.mp4Parte 2: Il test DK1 per riconoscere una grammatica LR(1) [11:35]
Parte 2: Il test DK1 per riconoscere una grammatica LR(1) [11:35]
lez-11-02.mp4Parte 3: Esercizio: applicazione del test DK1 [14:44]
Parte 3: Esercizio: applicazione del test DK1 [14:44]
lez-11-03.mp4Parte 4: Il parser di Earley per le grammatiche libere dal contesto [14:56]
Parte 4: Il parser di Earley per le grammatiche libere dal contesto [14:56]
lez-11-04.mp4Parte 5: Esempio di esecuzione del parser di Earley [29:01]
Parte 5: Esempio di esecuzione del parser di Earley [29:01]
lez-11-05.mp4Parte 6: Ricostruzione dell'albero sintattico dall'esecuzione del parser di Earley [8:03]
Parte 6: Ricostruzione dell'albero sintattico dall'esecuzione del parser di Earley [8:03]
lez-11-06.mp4