Esercizio 43
Preso un alfabeto Σ, definire formalmente l'insieme Σ*.
Dimostrare come, se si considera Σ={a,b,c}, gli elementi dell'insieme Σ* possano venir messi in corrispondenza biunivoca con i numeri naturali.
Esercizio 44
Dimostrare che, preso un alfabeto Σ (per esempio il Σ dell'esercizio precedente), i linguaggi su Σ non possono venir messi in corrispondenza biunivoca con i numeri naturali.
Esercizio 45 (NO a.a.17-18)
Usare il metodo di Diagonalizzazione per dimostrare che ci sono funzioni calcolabili che non sono primitive ricorsive.
Esercizio 46
Q = {q0,q1,q2,qF}
F = {qF}
stato iniziale = q0
e dalla seguente tabella di transizione:
a b blank
----------------------------------
q0 | a,q2,D | b,q1,D | |
-------------------------------
q1 | a,q0,D | b,q2,D | |
-------------------------------
q2 | a,q1,D | b,q2,D | blank,qF,I |
----------------------------------
E' possibile capire subito se questa macchina di turing
riconosce un linguaggio regolare? Perche'?
Esercizio 47
Dimostrare che un linguaggio non-regolare ha un numero infinito di stringhe.
Esercizio 48
Dimostrare formalmente che il linguaggio {an b | n≥0} coincide con il linguaggio riconosciuto dall'automa
Utilizzare il concetto di funzione di transizione δ e di funzione δ.
Si consideri che la funzione δ, puo' essere definita anche nel seguente modo:
δ(q,ε) = q
δ(q,ax) = δ(δ(q,a),x)
Per semplicita', si supponga di aver gia' dimostrato che le stringhe riconosciute dall'automa siano tutte della forma anb. Si dimostri quindi solamente che tutte quelle della forma anb sono riconosciute.
Esercizio 49
Si dimostri che esistono linguaggi che non possono essere generati da alcuna grammatica.
Esercizio 50
Si consideri la seguente grammatica G=({1,0}, {S,A,B}, P, S), dove P e' composto dalle produzioni
S --> A | BModificare le produzioni di G in modo che venga generato lo stesso linguaggio, ma la grammatica sia lineare destra.
A --> 0 | A1
B --> 011C | 111C
C --> ε | 01C
Esercizio 51
Fornire formalmente la definizione di derivazione diretta in una grammatica, quella di derivazione e quella di linguaggio generato da una grammatica.
Esercizio 52
Fornire l'automa a stati finiti che riconosca il seguente linguaggio
{s∈{0,1}* | s rappresenta un numero dispari in notazione posizionale binaria}.
Esercizio 53
Dimostrare che il linguaggio {ahbk | h,k≥0 , h>k } non e' regolare.
Esercizio 54
Sia data la rete stradale in figura.
a b c
A------->o------->o---->B
\ | ^\
\ | / |
\d | f/ |
\ e| / |
\ | / |
\ | / g|
\ | / |
v| / |
v/ h v
o<---------o
Fornire l'espressione regolare che rappresenta il linguaggio di tutti i percorsi da A a B (inclusi i cicli).
Esercizio 55
Si consideri la grammatica G = <{a,b,c},{S,A},P,S>, dove P e'
S → aSc | A Ac → bA | εDimostrare che
L(G) = {anbmcn-m | n>0, m>0, n≥m}
Esercizio 56
Fornire le definizioni di linguaggio decidibile e di linguaggio semidecidibile. Fornire informalmente un algoritmo di semidecisione per linguaggi di tipo 1 (contestuali).
Esercizio 57
Descrivere il formalismo delle espressioni regolari come definito dal testo di Ausiello.
Dire come e' possibile definire in tale formalismo il linguaggio contenente la sola stringa vuota.
Esercizio 58
Si consideri il seguente linguaggio L:
{anbmcn-m | n≥0, m≥0, n≥m}
Dimostrare formalmente, che L e' il
il linguaggio generato dalla grammatica seguente
S → aSc | A Ac → bA A → ε
Esercizio 59
Fornire la definizione di espressione regolare. Fornire inoltre l'espressione regolare
che rappresenta il linguaggio di tutte le stringhe lunghe 3 sull'alfabeto {a,b,c,d}.
Esercizio 60
Sia G1 una grammatica con il seguente insieme di produzioni:
S --> aS | b
e sia G2 una grammatica con il seguente insieme di produzioni:
S --> b | Ab
A --> Aa | a
Dimostrare che G1 e G2 sono equivalenti.
Esercizio 61
Dimostrare che il linguaggio
L = {ahbk | h,k>0, h>k}
non e' regolare.
Esercizio 62
Fornire la definizione formale di Grammatica di Chomsky. Definire formalmente le grammatiche di tipo 0,1,2 e 3.
Esercizio 63
Si consideri un insieme numerabile di simboli A e di dimostri che l'insieme delle stringhe di lunghezza finita di simboli di A e' un insieme numerabile. Lo si faccia descrivendo come sia possibile enumerare (cioe' come sia possibile costruire una lista infinita di) tutte e sole le strighe in questione.
Esercizio 64
Sia G1 = {{a,b,c},{S,A,B},P,S} dove P = { S → AAdcc, S → bbScc, A → cc }
Sia G2 = {{a,b},{S,A,B},P,S} dove P = { S → AAd, S → bbScc, aa → cAc }
Sia G3 = {{a,b,c},{S,A,B},P,S} dove P = { S → AAaa, ccSaa → bbScc, A → cAc }
Sia G4 = {{a,b,c},{S,A,B},P,S} dove P = { A → AAaa, B → bbScc, A → cBc }
Dire se quelle sopra definite sono grammatiche di Chomsky. Dire eventualmente a quale classe di grammatiche appartengono.
Esercizio 65
Fornire la definizione di grammatica formale. Fornire inoltre le definizioni di grammatica di tipo 0,1,2 e 3.
Esercizio 66
Definire una grammatica che generi il linguaggio {an bm cp | n = m ∨ m = p, n,m,p≥0} e dimostrare la sua correttezza.
Esercizio 67
Dimostrare che l'insieme dei linguaggi di tipo 3 e' numerabile.
(Supponiamo di sapere che i caratteri utilizzati nelle espressioni regolari, oltre ai simboli '*','+','(', ecc. siano presi da un insieme A numerabile; supponiamo inoltre di sapere che e' possibile generare tutte le stringhe di lunghezza finita sull'alfabeto A).
Esercizio 68
Dare la definizione di espressione regolare. Scrivere inoltre l'espressione regolare che rappresenta il linguaggio di tutte le stringhe sull'alfabeto {a,b,c,d} che terminano con "abb".
Esercizio 69
Sia G=({a,b,c},{S,A,B},P,S) dove P contiene le seguenti regole
S -> Ac, A -> AB | B, B -> aAb | ab.Dimostrare che la stringa aaabbbc appartiene al linguaggio generato da G.
Esercizio 70
Dimostrare che il linguaggio
L = {ahbk | h,k>0, h>k}
non e' regolare.
Esercizio 71
Costruire l'automa a stati finiti deterministico che accetta il linguaggio delle stringhe sull'alfabeto {a,b} con un numero pari di 'a' e un numero pari di 'b'.
(consideriamo pari il numero 0)
Fare l'esercizio considerando "dispari" al posto di "pari"
Esercizio 72
Sia L il linguaggio di tutte le stringhe sull.alfabeto {a,b} che hanno il carattere .b. in penultima posizione.
Scrivere un.espressione regolare che denota il linguaggio L; Definire una grammatica che genera il linguaggio L; Costruire un automa a stati finiti NON DETERMINISTICO che accetta il linguaggio L; Costruire un automa a stati finiti DETERMINISTICO che accetta il linguaggio L.
Esercizio 73
Fornire la definizione formale di Macchina di Turing deterministica.
Si consideri la seguente Macchina di Turing
M=< Γ, blank, Q, q0, F, δ >
con Γ = {a, b, c} Q = {q0, q1, qF} F = {qF} e la funzione δ cosi' definita
a b c blank
q0 q1 | a |D q0 | b | D q0 | c | D qF | blank |I
q1 q0 | a |D
Dire se la stringa .aabcaa. e. accettata o rifiutata da M. Giustificare la risposta.
Esercizio XX
Esercizio XX
Esercizio XX