Topic outline

  • Materiale Didattico

    Il libro di testo adottato dal corso è :
    John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
    Automi, linguaggi e calcolabilità, terza edizione
    Pearson Education Italia, 2018

    Come complemento al libro di testo, il corso utilizza inoltre:
    • un eserciziario con la soluzione di alcuni esercizi sugli argomenti svolti nel corso
    • un forum per lo scambio tra gli studenti ed il docente di informazioni tecniche, didattiche ed amministrative
  • Lezione 1

    Lunedì 30 settembre (ore 14:30-16:30)

    Presentazione del corso

    • Informazioni amministrative
    • Materiale didattico e programma

    Introduzione alla teoria degli automi

    • Esempi di modelli di calcolo
    • Modelli riconoscitivi e modelli generativi
    • Dimostrazione deduttiva
    • Altre tecniche di dimostrazione
    • Dimostrazione per induzione
    • Dimostrazione per induzione strutturale

    Materiale

    • Hopcroft et al., cap. 1
  • Lezione 2

    Martedì 01 ottobre (ore 08:30-10:30)

    Introduzione alla teoria degli automi

    • Mutua induzione
    • Nozioni di base della teoria dei linguaggi formali: stringhe e linguaggi
    • Linguaggi e problemi di decisione

    Materiale

    • Hopcroft et al., cap. 1
    • Lezione 3

      Giovedì 03 ottobre (ore 10:30-12:30)

      Automi a stati finiti

      • Automi a stati finiti deterministici (DFA)
      • Elaborazione di una stringa
      • Definizione matematica di DFA
      • Rappresentazioni alternative per DFA
      • Estensione funzione di transizione
      • Linguaggio accettato da DFA

      Materiale

      • Hopcroft et al., cap. 2
    • Lezione 4

      Lunedì 07 ottobre (ore 14:30-16:30)

      Automi a stati finiti

      • Automi a stati finiti nondeterministici (NFA)
      • Interpretazione "simultanea" ed interpretazione mediante "oracolo"
      • Definizione matematica di NFA
      • Estensione funzione di transizione
      • Linguaggio accettato da NFA
      • Esercizi

      Materiale

      • Hopcroft et al., cap. 2
      • Lezione 5

        Martedì 08 ottobre (ore 08:30-10:30)

        Automi a stati finiti

        • Equivalenza DFA e NFA
        • Crescita esponenziale degli stati
        • DFA parziali
        • Esercizi su DFA
        • Applicazioni: ricerca testuale

        Materiale

        • Hopcroft et al., cap. 2
        • Lezione 6

          Giovedì 10 ottobre (ore 10:30-12:30)

          Automi a stati finiti

          • NFA con epsilon-transizioni (e-NFA)
          • Definizione matematica di e-NFA
          • Definizione di e-chiusura
          • Estensione funzione di transizione
          • Linguaggio accettato da e-NFA
          • Equivalenza di e-NFA e DFA

          Esericizi

          • Scrivere un DFA \(M\) che riconosca il linguaggio \(L\) di tutte le stringhe in \( \{0,1\}^\ast \) aventi un numero dispari di occorrenze del simbolo 1; dimostrare che \( L(M) = L \) (esercizio 1.1 dell'eserciziario)
          • Sia \(\#_a(w)\) il numero di occorrenze del carattere \(a\) nella stringa \(w\); scrivere un DFA che riconosca il linguaggio \( L = \{ w \; | \; w \in \{a,b\}^\ast, \) per ciascun prefisso \(x\) di \(w\) vale \( \#_b(x) \leq \#_a(x) \leq \#_b(x)+2 \} \) (esercizio 2, terza domanda, dal tema d'esame del 13/09/2019)

          Materiale

          • Hopcroft et al., cap. 2
          • Lezione 7

            Lunedì 14 ottobre (ore 14:30-16:30)

            Espressioni regolari

            • Operazioni su linguaggi
            • Definizione induttiva di espressione regolare
            • Precedenza operatori
            • Esercizi
            • Costruzione di espressioni regolari da DFA per eliminazione di stati

            Materiale

            • Hopcroft et al., cap. 3
          • Lezione 8

            Martedì 15 ottobre (ore 08:30-10:30)

            Espressioni regolari

            • Costruzione di e-NFA da espressioni regolari
            • Equivalenza di FA e espressioni regolari
            • Applicazioni delle espressioni regolari
            • Leggi algebriche per le espressioni regolari

            Materiale

            • Hopcroft et al., cap. 3
            • Lezione 9

              Giovedì 17 ottobre (ore 10:30-12:30)

              Proprietà dei linguaggi regolari

              • Il pumping lemma per i linguaggi regolari
              • Esercizi sul pumping lemma

              Materiale

              • Hopcroft et al., cap. 4
            • Lezione 10

              Lunedì 21 ottobre (ore 14:30-16:30)

              Proprietà dei linguaggi regolari

              • Proprietà di chiusura dei linguaggi regolari: unione, concatenazione, operatore di Kleene, complemento
              • Automa intersezione
              • Chiusura rispetto alla differenza insiemistica e all’applicazione dell'operatore reverse

              Esercizi

              • Utilizzando l'induzione strutturale, dimostrare che se una espressione regolare \(R\) non contiene l'operatore \(\ast\), allora \(L(R)\) è un linguaggio finito

              Materiale

              • Hopcroft et al., cap. 4
              • Lezione 11

                Martedì 22 ottobre (ore 08:30-10:30)

                Proprietà dei linguaggi regolari

                • Test sul problema dell'intersezione tra linguaggi regolari e non
                • Chiusura rispetto all’applicazione di omomorfismo

                Esercizi

                • Dimostrare che i seguenti linguaggi non sono regolari: \( L_{=} = \{ a^{n} b^{n} \; | \; n \geq 1 \} \), \( L_{>} = \{ a^{n} b^{m} \; | \; n, m \geq 1, \; n > m \} \), \( L_{<} = \{ a^{n} b^{m} \; | \; n, m \geq 1, \; n < m \} \), \( L_{\neq} = \{ a^{n} b^{m} \; | \; n,m \geq 1, \; n \neq m \} \)

                Materiale

                • Hopcroft et al., cap. 4
                • Lezione 12

                  Giovedì 24 ottobre (ore 10:30-12:30)

                  Proprietà dei linguaggi regolari

                  • Complessità delle conversioni
                  • Test per il linguaggio vuoto
                  • Test per appartenenza di una stringa ad un linguaggio
                  • Stati equivalenti in un DFA

                  Esercizi

                  • Specificare un DFA \( M \)per il linguaggio \( L = \{ (ab)^n \; | \; n \geq 0 \} \). Usando la mutua induzione, dimostrare che \( L = L(M) \)
                  • Esercizio su operazioni insiemistiche per i linguaggi regolari

                  Materiale

                  • Hopcroft et al., cap. 4
                  • Lezione 13

                    Lunedì 28 ottobre (ore 14:30-16:30)

                    Proprietà dei linguaggi regolari

                    • Algoritmo per il calcolo degli stati equivalenti
                    • Equivalenza di linguaggi regolari
                    • Algoritmo di minimizzazione di DFA

                    Esercizi

                    • Verificare se il linguaggio \( L_1 = \{w \; | \; w \in \{a,b\}^*, \; \#_b(w)  \leq  \#_a(w)  ≤  2 \#_b(w) \} \) è regolare
                    • Verificare se il linguaggio \( L_2 = \{w \; | \; w \in \{a,b\}^*, \; \#_a(w)  \neq  \#_b(w), \;  \#_a(w)  \neq  2 \#_b(w) \} \) è regolare

                    Materiale

                    • Hopcroft et al., cap. 4
                    • Lezione 14

                      Martedì 29 ottobre (ore 08:30-10:30)

                      Grammatiche context-free

                      • Esempio linguaggio context-free
                      • Definizione grammatica context-free
                      • Inferenza ricorsiva
                      • Derivazione, derivazione sinistra e derivazione destra
                      • Linguaggio di una grammatica

                      Materiale

                      • Hopcroft et al., cap. 5
                    • Lezione 15

                      Giovedì 31 ottobre (ore 10:30-12:30)

                      Esercizi

                      • Grammatica context-free per stringhe con parentesi bilanciate
                      • Grammatica context-free per il linguaggio \( L = \{ w \; | \; w = a^p b^q c^r, \; q \neq r \} \)

                      Grammatiche context-free

                      • Forme sentenziali di una grammatica context-free
                      • Alberi sintattici: definizione ed esempi

                      Materiale

                      • Hopcroft et al., cap. 5
                      • Lezione 16

                        Lunedì 4 novembre (ore 14:30-16:30)

                        Grammatiche context-free

                        • Equivalenza tra inferenza ricorsiva, albero sintattico e derivazione
                        • Ambiguità in grammatiche e linguaggi
                        • Derivazioni canoniche
                        • Ambiguità inerente

                        Esercizi

                        • Dimostrare per mutua induzione che una grammatica context-free con produzioni \( S \rightarrow aS \; | \; aB \), \( B \rightarrow bB \; | \; bC \), \( C \rightarrow cC \; | \; c \) genera il linguaggio \( L = \{ w \; | \; w = a^p b^q c^r, p,q,r \geq 1 \} \)

                        Materiale

                        • Hopcroft et al., cap. 5
                        • Lezione 17

                          Martedì 5 novembre (ore 8:30-10:30)

                          Grammatiche context-free

                          • Da espressione regolare a CFG
                          • Da automa a stati finiti a CFG

                          Automi push-down

                          • Esempio di automa push-down
                          • Definizione di automa push-down
                          • Rappresentazione grafica della funzione di transizione
                          • Descrizione istantanea e passo di computazione
                          • Definizione di computazione

                          Materiale

                          • Hopcroft et al., cap. 6
                        • Lezione 18

                          Giovedì 7 novembre (ore 10:30-12:30)

                          Automi push-down

                          • Proprietà delle computazioni
                          • Accettazione per stato finale
                          • Accettazione per stack vuoto
                          • Trasformazione da stack vuoto a stato finale
                          • Trasformazione da stato finale a stack vuoto
                          • Trasformazione da CFG a PDA

                          Materiale

                          • Hopcroft et al., cap. 6
                          • Lezione 19

                            Lunedì 11 novembre (ore 14:30-16:30)

                            Automi push-down

                            • Trasformazione da CFG a PDA
                            • Trasformazione da PDA a CFG (solo idea base)

                            Esercizi

                            • Dimostrare per mutua induzione che una grammatica context-free con produzioni \( S \rightarrow SS \; | \; (S) \; | \; ( \; ) \) genera il linguaggio delle stringhe con parentesi tonde bilanciate
                            • Sia \( L = \{ a^nb^n \; | \; n \geq 1 \} \), \( L' = \{ a,b \}^+ \). Il linguaggio \( L' \cdot L \cdot L' \) è regolare?

                            Materiale

                            • Hopcroft et al., cap. 6
                            • Lezione 20

                              Martedì 12 novembre (ore 8:30-10:30)

                              Proprietà dei linguaggi context-free

                              • Eliminazione simboli inutili
                              • Algoritmo per i simboli generatori
                              • Algoritmo per i simboli raggiungibili
                              • Algoritmo per i simboli annullabili
                              • Eliminazione epsilon-produzioni
                              • Algoritmo per le coppie unitarie

                              Esercizi

                              • Dimostrare che il linguaggio \( L = \{ w \; | \; w \in \{a,b\}^\ast, \; \#_a(w) \neq \#_b(w) \} \) è context-free (suggerimento: definire un PDA \(P\) che accetta per stato finale tale che \(L(P) = L\) )

                              Materiale

                              • Hopcroft et al., cap. 7
                            • Lezione 21

                              Giovedì 14 novembre (ore 10:30-12:30)

                              Proprietà dei linguaggi context-free

                              • Eliminazione produzioni unitarie
                              • Semplificazione di una CFG
                              • Forma normale di Chomsky
                              • Pumping lemma per i CFL
                              • Esempi di applicazione
                              • Proprietà dei linguaggi context-free derivanti dal pumping lemma

                              Materiale

                              • Hopcroft et al., cap. 7
                            • Lezione 22

                              Lunedì 18 novembre (ore 14:30-16:30)

                              Proprietà dei linguaggi context-free

                              • Chiusura rispetto alla applicazione dell'operatore di sostituzione
                              • Applicazioni del teorema di sostituzione
                              • Chiusura rispetto all'operatore di inversione di stringhe
                              • Intersezione tra CFL
                              • Intersezione tra CFL e linguaggi regolari

                              Esercizi

                              • Dimostrare il seguente enunciato: dato un linguaggio regolare \(L\), esiste una costante \(n\) tale che, per ogni \(z \in L\) con \(|z| \geq n\), esiste una fattorizzazione \(z = uxyw\) con \(|x|, |y| \geq 1\) e \(|xy| \leq n\), tale che \(uyxw \in L\)

                              Materiale

                              • Hopcroft et al., cap. 7
                              • Lezione 23

                                Martedì 19 novembre (ore 8:30-10:30)

                                Proprietà dei linguaggi context-free

                                • Altre proprietà di chiusura per i linguaggi context-free
                                • Analisi computazionale delle trasformazioni su CFG e PDA
                                • Test per il linguaggio vuoto e algoritmo per il calcolo dei simboli generatori
                                • Algoritmo di riconoscimento CYK
                                • Alcuni problemi indecidibili per i linguaggi context-free

                                Applicazioni

                                • Probabilistic finite-state automata (PFA)
                                • Finite-state transducers (FST)
                                • Hidden Markov models (HMM)

                                Materiale

                                • Hopcroft et al., cap. 7
                                • Lezione 24

                                  Giovedì 21 novembre (ore 10:30-12:30)

                                  Macchine di Turing

                                  • Macchina di Turing (TM)
                                  • Descrizione istantanea di una TM
                                  • Computazione di una TM
                                  • Esempi

                                  Esercizi

                                  • Dimostrare che il linguaggio \( L = \{ a^n b^{n^2} \; | \; n \geq 1 \} \) non è CFL
                                  • Test sulle proprietà di chiusura dei linguaggi regolari (esercizio 3 dal tema d'esame del 13/02/2019)

                                  Materiale

                                  • Hopcroft et al., cap. 8
                                  • Appunti della lezione
                                • Lezione 25

                                  Lunedì 25 novembre (ore 14:30-16:30)

                                  Macchine di Turing

                                  • TM con output
                                  • Linguaggio accettato per stato finale
                                  • Linguaggio accettato per arresto
                                  • Linguaggi ricorsivi e linguaggi ricorsivamente enumerabili

                                  Esercizi

                                  • Esercizio sulla minimizzazione di DFA (esercizio 1 dal tema d'esame del 13/02/2019)
                                  • Determinare se i linguaggi \( L_1 = \{ a^n b a^n b a^m\; | \; n,m \geq 1, \; m \geq n \} \) e \( L_2 = \{ a^n b a^p b a^m\; | \; n,p,m \geq 1, \; m \geq n \} \) siano CFL (esercizio 2 dal tema d'esame del 13/02/2019)

                                  Materiale

                                  • Hopcroft et al., cap. 8
                                  • Appunti della lezione
                                  • Lezione 26

                                    Martedì 26 novembre (ore 8:30-10:30)

                                    Macchine di Turing

                                    • Stato come memoria interna finita ad accesso random
                                    • Numero finito di tracce sul nastro
                                    • Utilizzo di subroutine
                                    • TM multi-nastro
                                    • TM nondeterministica
                                    • TM con nastro semi-finito

                                    Applicazioni

                                    • Recurrent neural network (RNN)
                                    • Long short-term memory network (LSTM)
                                    • Rappresentazione distribuita
                                    • Relazione con 1-counter automata

                                    Materiale

                                    • Hopcroft et al., cap. 8
                                    • Appunti della lezione
                                    • Lezione 27

                                      Giovedì 28 novembre (ore 10:30-12:30)

                                      Macchine di Turing

                                      • TM con nastro semi-finito
                                      • TM multi-stack

                                      Indecidibilità

                                      • Indicizzazione delle stringhe
                                      • Codifica ed indicizzazione delle TM
                                      • Linguaggio di diagonalizzazione

                                      Materiale

                                      • Hopcroft et al., cap. 8
                                      • Hopcroft et al., cap. 9
                                    • Lezione 28

                                      Lunedì 02 dicembre (ore 14:30-16:30)

                                      Indecidibilità

                                      • Proprietà dei linguaggi ricorsivi
                                      • Proprietà dei linguaggi RE
                                      • Linguaggio universale
                                      • TM universale
                                      • Il linguaggio universale è in RE ma non in REC

                                      Esercizi sui linguaggi context-free

                                      • Sia \(L\) un linguaggio context-free; il linguaggio \( L' = \{ w \; | \; w \in L, \; |w| = 2n, \; n \geq 0 \} \) è ancora un linguaggio context-free?
                                      • Dato un linguaggio \(L\), definiamo \(\pi(L)\) come il linguaggio ottenuto permutando in tutti i modi possibili tutte le stringhe in \(L\). Sia \(L\) un linguaggio regolare. Il linguaggio \(\pi(L)\) è sempre un linguaggio context-free?

                                      Materiale

                                      • Hopcroft et al., cap. 9
                                      • Appunti della lezione
                                      • Lezione 29

                                        Martedì 03 dicembre (ore 8:30-10:30)

                                        Indecidibilità

                                        • Il problema dell'arresto di una TM su un input assegnato
                                        • Nozione di riduzione
                                        • Il linguaggio \( L_{ne} \) delle TM che accettano linguaggi non vuoti
                                        • Il linguaggio \( L_{e} \) delle TM che accettano linguaggi vuoti
                                        • Il linguaggio \( L_{ne} \) è RE

                                        Esercizi sui linguaggi context-free

                                        • Dimostrare che il linguaggio \( L = \{ ww^Rw \; | \; w \in \{0,1\}^\ast \} \) non è CFL

                                        Materiale

                                        • Hopcroft et al., cap. 9
                                        • Appunti della lezione
                                        • Lezione 30

                                          Giovedì 5 dicembre (ore 10:30-12:30)

                                          Indecidibilità

                                          • Il linguaggio \( L_{ne} \) non è in REC
                                          • Il linguaggio \( L_{e} \) non è in RE
                                          • Proprietà dei linguaggi generati da TM
                                          • Teorema di Rice

                                          Esercizi

                                          • Stabilire se i seguenti linguaggi siano regolari o meno, dove \( \Sigma = \{a,b\} \): \(L_1 = \{ bbxbbx^R \; | \; x \in \Sigma^\ast \}\), \(L_2 = \{ bbx \; | \; x \in \Sigma^\ast \} \cdot \{ bbx^R | x \in \Sigma^\ast \} \), \( L_3 = \{ bbx \; | \; x \in \Sigma^\ast \} \cdot L_1 \cdot \{ bbx^R \; | \; x \in \Sigma^\ast \}\) (esercizio 2 dal tema d'esame del 28 giugno 2019)

                                          Materiale

                                          • Hopcroft et al., cap. 9
                                          • Appunti della lezione
                                          • Lezione 31

                                            Lunedì 9 dicembre (ore 14:30-16:30)

                                            Indecidibilità

                                            • Problema di Post (PCP) e problema di Post modificato (MPCP)
                                            • Riduzione da MPCP a PCP (solo enunciato)
                                            • Riduzione dal linguaggio universale a MPCP (idea base)
                                            • Riduzione da PCP al problema dell'ambiguità di un CFL

                                            Esercizi

                                            • Applicare l'algoritmo CYK alla stringa \( w = bbabbbc \) ed alla CFG avente le produzioni \(S \rightarrow AC\), \(A \rightarrow BA \; | \; a\), \(B \rightarrow b\), \(C \rightarrow BC \; | \; c\) (esercizio 3 dal tema d'esame del 28 giugno 2019)
                                            • Specificare una macchina di Turing che accetta il linguaggio \( L = \{ w \; | \; w \in \{ a, b \}^\ast, \; w = a^nb^{2n}, \; n \geq 0 \} \) (esercizio 4 dal tema d'esame del 28 giugno 2019)

                                            Materiale

                                            • Hopcroft et al., cap. 9
                                            • Appunti della lezione
                                            • Lezione 32

                                              Martedì 10 dicembre (ore 8:30-10:30)

                                              Intrattabilità

                                              • Problemi intrattabili
                                              • Complessità di tempo di una TM
                                              • Algoritmi polinomiali
                                              • Analisi della complessità di una TM

                                              Applicazioni

                                              • Applicazioni delle espressioni regolari
                                              • Tools e linguaggi di programmazione che utilizzano espressioni regolari
                                              • Back-reference
                                              • Uso di espressioni regolari in attacchi di tipo DoS

                                              Esercizi

                                              • Test sulle proprietà di chiusura dei linguaggi REC e dei linguaggi RE (esercizio 5 dal tema d'esame del 28 giugno 2019)

                                              Materiale

                                              • Hopcroft et al., cap. 10
                                              • Appunti della lezione
                                            • Lezione 33

                                              Giovedì 12 dicembre (ore 10:30-12:30)

                                              Intrattabilità

                                              • Algoritmi polinomiali nondeterministici
                                              • Riduzioni polinomiali
                                              • Problemi NP-completi e problemi NP-hard
                                              • Espressioni booleane
                                              • Soddisfacibilità ed il problema SAT

                                              Esercizi

                                              • Sia \(L_p\) il linguaggio di tutte le stringhe in \(\{0,1\}^\ast\) aventi lunghezza pari. Sia inoltre \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_p \subsetneq L \} \). Stabilire se \(L_{\cal P}\) è un linguaggio ricorsivo. Cosa posso dire riguardo al linguaggio \(L_{\overline{{\cal P}}}\)? (esercizio 4 dal tema d'esame del 22 gennaio 2019)
                                              • Siano \(L_1\) e \(L_2\) due linguaggi ricorsivi. Il linguaggio \(L_1 L_2\) (concatenazione) è ancora ricorsivo? (esercizio 5(a) dal tema d'esame del 22 gennaio 2019)

                                              Materiale

                                              • Hopcroft et al., cap. 10
                                              • Appunti della lezione
                                              • Lezione 34

                                                Lunedì 16 dicembre (ore 14:30-16:30)

                                                Intrattabilità

                                                • Codifica delle espressioni booleane
                                                • Teorema di Cook (idea base)

                                                Esercizi

                                                • Sia \(L_1\) un linguaggio ricorsivo e sia \(L_2\) un linguaggio ricorsivamente enumerabile. Il linguaggio \(L_1 \cap L_2\) è ancora ricorsivo? (esercizio 5(b) dal tema d'esame del 22 gennaio 2019)
                                                • Sia \(L = \{enc(M, M') \; | \; L(M) \subseteq L(M') \}\). Il linguaggio \(L\) è ricorsivamente enumerabile? (esercizio 5(c) dal tema d'esame del 22 gennaio 2019)

                                                Materiale

                                                • Hopcroft et al., cap. 10
                                                • Appunti della lezione
                                                • Lezione 35

                                                  Martedì 17 dicembre (ore 8:30-10:30)

                                                  Intrattabilità

                                                  • Forme normali per espressioni booleane
                                                  • Problemi CSAT e 3SAT
                                                  • Problema dell'insieme indipendente
                                                  • IS è un problema NP-completo

                                                  Applicazioni delle grammatiche context-free

                                                  • Grammatiche alle dipendenze
                                                  • Compositional vector grammars
                                                  • Sentiment Analysis

                                                  Esercizi

                                                  • Per un linguaggio \(L\) definito su \(\Sigma\) definiamo \(prf(L) = \{ w \; | \; wx \in L, \; w \in \Sigma^\ast, \; x \in \Sigma^+ \}\). La classe RE gode della proprietà di chiusura rispetto all'operatore \(prf\)? (esercizio 3.3 dell'eserciziario)
                                                  • Sia \(L_1\) un linguaggio ricorsivo non context-free e sia \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; L \subseteq L_1 \}\). Stabilire se \(L_{\cal P}\) sia un linguaggio ricorsivo.(esercizio 3.4 dell'eserciziario)

                                                  Materiale

                                                  • Hopcroft et al., cap. 10
                                                  • Appunti della lezione
                                                  • Lezione 36

                                                    Giovedì 19 gennaio (ore 10:30-12:30)

                                                    Intrattabilità

                                                    • Problema copertura per nodi
                                                    • Problema del circuito Hamiltoniano orientato

                                                    Esercizi

                                                    • Siano \(L_1\) ed \(L_2\) due linguaggi ricorsivi. Il linguaggio \(L_3 = \{ w \; | \; w = xyz, \; xz \in L_1, \; y \in L_2 \}\) è ricorsivo? (esercizio 5(a) dal tema d'esame del 13 settembre 2019)
                                                    • Sia \(L_= = \{ enc(M, M') \; | \; L(M) \cup L(M') = \emptyset \}\). Il linguaggio \(L\) è ricorsivamente enumerabile? (esercizio 5(b) dal tema d'esame del 13 settembre 2019)
                                                    • Sia \(L = \{ enc(M, M') \; | \; L(M) \cup L(M') \neq \emptyset \}\). Il linguaggio \(L\) è ricorsivamente enumerabile? (esercizio 5(c) dal tema d'esame del 13 settembre 2019)
                                                    • Sia \(L_1\) un insieme finito e sia \( {\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_1 \cap L \not = \emptyset \}\). Stabilire se \(L_{\cal P}\) è ricorsivo e se è ricorsivamente enumerabile (esercizio 3.7 dell'eserciziario)

                                                    Materiale

                                                    • Hopcroft et al., cap. 10
                                                    • Appunti della lezione
                                                    • Programma corso

                                                      Il programma del corso è basato sul libro di testo adottato. Alcuni argomenti segnalati esplicitamente nel programma devono essere integrati con i lucidi delle lezioni, disponibili sul sito del corso stesso.
                                                    • Temi d'esame dai precedenti appelli

                                                      In questo box vengono pubblicati i temi d'esame svolti nei precedenti appelli.