Parte 1: Introduzione ed organizzazione del corso [::]

Parte 2: Le origini dell'Informatica Teorica [24:59] 

Parte 3: Esempio di un programma a stati finiti [15:55] 

Parte 1: Stringhe e linguaggi [13:38]

Parte 2: Automi a stati finiti deterministici (DFA) [24:22]

Parte 3: Linguaggi regolari e loro chiusura rispetto ad unione ed intersezione [26:25]

Parte 4: Automi a stati finiti non deterministici [24:49]

Parte 1: Equivalenza di DFA e NFA [15:33]

Parte 2: Esercizio: derivazione di un DFA equivalente ad un NFA [16:18]

Parte 3: Dimostrazioni di chiusura dei linguaggi regolari con NFA [15:41]

Parte 4: Espressioni regolari (REX) [15:46]

Parte 5: Le espressioni regolari generano linguaggi regolari [12:52]

Parte 6: Esercizi: costruzione di automi corrispondenti a espressioni regolari [14:51]

Parte 1: Automi a stati finiti non deterministici generalizzati  (GNFA) [18:23]

Parte 2: Conversione da GNFA ad espressione regolare [18:53]

Parte 3: Esercizio: conversione da DFA ad espressione regolare [20:35]

Parte 4: Il "pumping lemma" per i linguaggi regolari (enunciato) [19:01]

Parte 5: Il "pumping lemma" per i linguaggi regolari (dimostrazione) [18:18]

Parte 1: Applicazione del pumping lemma [18:02]

Parte 2: Esercizi: dimostrare non regolarità usando il pumping lemma [17:07]

Parte 3: Esercizi: altre applicazioni del pumping lemma  [13:01]

 Parte 4: Chiusura dei linguaggi regolari rispetto a complemento e inverso  [18:14]

 Parte 5: Chiusura dei linguaggi regolari rispetto all'omomorfismo  [18:02]

Parte 6: Introduzione alle grammatiche libere dal contesto (CFG)  [10:55]

Parte 1: Linguaggi liberi dal contesto (CFL)  [19:25]

Parte 2: Chiusura dei CFL rispetto all'unione. Alberi sintattici  [20:39]

Parte 3: Ambiguità di CFG e CFL. Forma normale di Chomsky  [18:07]

Parte 4: Esercizio: conversione di una grammatica in forma normale di Chomsky  [15:03]

Parte 5: Automi a pila (PDA)  [18:20]

Parte 1: Esercizio: costruzione di un PDA che riconosce un CFL [20:47]

Parte 2: Esercizi: ulteriori esempi di PDA [14:48]

Parte 3: Equivalenza tra CFG e PDA: costruzione del PDA per una generica CFG [22:20]

Parte 4: Equivalenza tra CFG e PDA: costruzione di una CFG per un generico PDA (idea) [26:22]

Parte 5: Equivalenza tra CFG e PDA: costruzione di una CFG per un generico PDA (dimostr.) [19:37]

Parte 1: Il "pumping lemma" per i linguaggi liberi dal contesto (enunciato) [13:49]

Parte 2: Il "pumping lemma" per i linguaggi liberi dal contesto (dimostrazione) [13:30]

Parte 3: Esercizi: applicazioni del pumping lemma per CFL [16:34]

Parte 4: Proprietà di chiusura di CFL rispetto a vari operatori [11:53]

Parte 5: Automi a pila deterministici (DPDA) e linguaggi CFL deterministici (DCFL) [20:08]

Parte 6: Proprietà di chiusura di DCFL rispetto a diversi operatori [18:05]

Parte 1: Linguaggi liberi dal contesto con marcatore di fine stringa [12:44]

Parte 2: Linguaggi liberi dal contesto con marcatore di fine stringa (cont.) [21:53]

Parte 3: Riduzioni e maniglie per le grammatiche libere dal contesto [18:23]

Parte 4: Definizione delle grammatiche libere dal contesto deterministiche (DCFG) [18:14]

Parte 5: Il test DK: costruzione degli automi K e DK [21:36]

Parte 6: Esempio di costruzione dell'automa K [11:12]

Parte 1:  Esempio di costruzione dell'automa DK [14:31]

Parte 2:  Il funzionamento del test DK  [13:11]

Parte 3:  Esercizi sul test DK  [14:15]

Parte 4: Per ogni grammatica DCFG esiste un automa a pila deterministico equivalente  [24:28]

Parte 5: Per ogni DPDA che riconosce un linguaggio marcato esiste una DCFG equivalente [18:45]

Parte 6: La classe dei linguaggi generati da grammatiche libere dal contesto deterministiche [11:15]

Parte 1:  Le grammatiche LR(k) [13:05]

Parte 2:  Il test DK1 per riconoscere una grammatica LR(1) [11:35]

Parte 3:  Esercizio: applicazione del test DK1 [14:44]

Parte 4:  Il parser di Earley per le grammatiche libere dal contesto [14:56]

Parte 5:  Esempio di esecuzione del parser di Earley [29:01]

Parte 6:  Ricostruzione dell'albero sintattico dall'esecuzione del parser di Earley [8:03]