Esercizi della 1a settimana
Esercizio 1.1
Definire un automa finito per il linguaggio sull'alfabeto {a,b} di
tutte le parole che finiscono per aa.
Esercizio 1.2
Definire un automa finito per il linguaggio sull'alfabeto {a,b} di
tutte le parole che contengono
aaa.
Esercizio 1.3
Definire un automa finito per il linguaggio sull'alfabeto {a,b} di
tutte le parole che iniziano o terminano per
ab.
Esercizio 1.4
Definire un automa finito per il linguaggio sull'alfabeto {a,b} di
tutte le parole in cui il numero di a
e' multiplo di 2 mentre
il numero di b e' multiplo di 3.
Esercizio 1.5
Definire un automa finito per il linguaggio sull'alfabeto {a,b} di
tutte le parole in cui il quarto simbolo a partire da destra e' una b.
Esercizio 1.6
Definire un automa per il linguaggio sull'alfabeto {0,1} di parole che iniziano
per 1 e corrispondono a numeri binari multipli di 5.
Esercizi della 2a settimana
Esercizio 2.1
Definire un NFA per il linguaggio sull'alfabeto {a,b} di
tutte le parole che terminano per abaa.
Trasformarlo in un DFA.
Esercizio 2.2
Definire un NFA per il linguaggio sull'alfabeto {a,b} di
tutte le parole che contengono sia aa che bb.
Trasformarlo in un DFA.
Esercizio 2.3
Dal libro di testo Es. 2.3.3
Esercizio 2.4
Dal libro di testo Es. 2.3.4
Esercizi della 3a settimana
Esercizio 3.1
Definire un epsilon-NFA per il linguaggio sull'alfabeto {a,b} di
tutte le parole che iniziano per aa e sono di lunghezza
pari oppure di lunghezza
dispari e terminano per bb.
Trasformarlo in un DFA.
Esercizio 3.2
Esercizio 2.5.1 dal libro di testo.
Esercizio 3.3
Esercizio 2.5.2 dal libro di testo.
Esercizi della 4a settimana
Esercizio 4.1
Esercizio 3.2.2 dal libro di testo.
Esercizio 4.2
Esercizio 3.2.3 dal libro di testo.
Esercizio 4.3
Esercizio 3.2.4 dal libro di testo.
Applicare la trasformazione canonica da RE a e-NFA e poi convertire in
DFA alle seguenti espressioni regolari.
a)01*
b)(0+1)01
c)00(0+1)*
Esercizi della 5a settimana
Esercizio 5.1
Esercizio 4.1.1 dal libro di testo
Esercizi della 6a settimana
Esercizio 6.1
Data la seguente espressione regolare E=(a+b)*abb
-definire un ε-NFA che riconosce il linguaggio di E
-definire un DFA equivalente
-applicare l'algoritmo di minimizzazione a tale DFA.
Esercizio 6.2
Data la seguente espressione regolare E=(a+ε)(b+c)*(bc+ab)*
-definire un ε-NFA che riconosce il linguaggio di E
-definire un DFA equivalente
-applicare l'algoritmo di minimizzazione a tale DFA.
Esercizi della 7a settimana
Esercizio 7.1
Scrivere una grammatica context-free per il
seguente linguaggio: "parole con lo stesso numero di a
e di b".
Esercizio 7.2
Scrivere una grammatica context-free per il
seguente linguaggio L={w c wR| w ∈ {a,b}*}
Esercizio 7.3
Scrivere una grammatica context-free per il
seguente linguaggio L={anbm| m>n, n>0}
Esercizio 7.4
Scrivere una grammatica context-free per il
seguente linguaggio L={anbncmdm| m, n>0}
Esercizio 7.5
Scrivere una grammatica context-free per il
seguente linguaggio L={anbmcmdn| m, n>0}
Esercizi della 8a settimana
Esercizio 8.1
Scrivere un'automa a pila per il
seguente linguaggio: "parole con lo stesso numero di a
e di b".
Esercizio 8.2
Scrivere un'automa a pila per il
seguente linguaggio L={w c wR| w ∈ {a,b}*}
Esercizio 8.3
Scrivere un'automa a pila per il
seguente linguaggio L={anbm| m>n, n>0}
Esercizio 8.4
Scrivere un'automa a pila per il
seguente linguaggio L={anbncmdm| m, n>0}
Esercizio 8.5
Scrivere un'automa a pila per il
seguente linguaggio L={anbmcmdn| m, n>0}
Esercizi della 9a settimana
Esercizio 9.1
Scrivere una macchina di Turing per il linguaggio
L={anbncn|n>0}
Esercizio 9.2
Scrivere una macchina di Turing per il linguaggio
L={ww |w∈ {a,b}*}
Esercizi della 10a settimana
Esercizio 10.1
Scrivere una macchina di Turing multinastro per il linguaggio
L={anbncn|n>0}
Esercizio 10.2
Scrivere una macchina di Turing multinastro per il linguaggio
L={ww |w∈ {a,b}*}