Provare che il seguente linguaggio non è context free.
L = {akbkci | i ≤ k}
Il Pumping Lemma dei CFL dice:
Se L è un linguaggio libero dal contesto allora ∀ stringa in L, di lunghezza ≥ n è possibile scomporla in z = uvwxy con le segunti proprietà:
- |vwx| ≤ n
- vx ≠ ε
- ∀ i ≥ 0 la stringa uviwxiy ∈ L
Quindi, per dimostrare che L non è context free, è sufficiente scegliere una parola tale che per qualunque costante n sia possibile trovare una i che faccia uscire dal linguaggio la parola pompata.
Scelgo la parola z = anbncn (∈ L).
Per ogni split z = uvwxy i casi possibili sono i seguenti:
vexcontengono solo 'a' (almeno una 'a' invx)vexcontengono solo 'b' (almeno una 'b' invx)vcontiene solo 'a' excontiene solo 'b'vexcontengono solo 'c' (almeno una 'c' invx)vcontiene solo 'b' excontiene solo 'c'
Nei casi 1, 2, 3 basta prendere i = 0. Ad esempio nel caso 1 la stringa uv0wx0y avrebbe rimosso delle 'a', ma nessuna 'b', quindi la parola non può essere in L.
Nel caso 3 sarà tolta almeno una 'a' e una 'b' quindi la stringa risultante avrà un numero di 'c' maggiore di quello di 'a' e 'b'.
Nel caso 4 scelgo i = 2. La stringa risultante avrà più 'c' che 'a' e 'b'.
Anche nel caso 5, con i = 2, aggiungendo 'b' queste non matcheranno più il numero di 'a' che resta inalterato. Allo stesso modo, aggiungendo 'c' il numero diventerà maggiore delle 'a'.
In nessuno di questi casi la stringa pompata ∈ L. Quindi L non può essere un linguaggio libero dal contesto.
Rendere la grammatica in forma CNF:
- S => aAa | bBb | ε
- A => C | a
- B => C | b
- C => CDE | ε
- D => A | B | ab
Le variabili annullabili sono: Z = {S, C, A, B, D}
- S => aAa | aa | bBb | bb
- A => C | a
- B => C | b
- C => CDE | DE | CE | E;
- D => A | B | ab
Coppie unitarie:
- (A, A) => (A, C), (A, E)
- (B, B) => (B, C), (B, E)
- (C, C) => (C, E)
- (D, D) => (D, A), (D, B), (D, C), (D, E)
- (S, S) => /
Quindi ∀(A, B) coppia unitaria, aggiungiamo ad A ogni produzione A → α, dove B → α è una produzione non unitaria.
Sostituisco e ottengo:
- S => aAa | aa | bBb | bb
- A => a | CDE | DE | CE
- B => b | CDE | DE | CE
- C => CDE | DE | CE
- D => ab | a | b | CDE | DE | CE
Generatori π = {a, b, S, A, B, D}
C non è generatore perchè non contiene almeno una produzione costituita da tutti simboli generatori (anche terminali). E non è generatore perchè non ha nessuna produzione.
Quindi buttando via C ed E e tutte le produzioni che sontengono queste variabili, resta:
- S => aAa | aa | bBb | bb
- A => a
- B => b
- D => ab | a | b
I simboli raggiungibili da S sono: R = {S, A, B, a, b}.
D non è raggiungibile, e quindi posso eliminarlo, includendo tutte le produzioni che lo includono:
- S => aAa | aa | bBb | bb
- A => a
- B => b
- S => AAA | AA | BBB | BB
- A => a
- B => b
Che diventa:
- S => AC | AA | BD | BB
- A => a
- B => b
- C => AA
- D => BB
Considerando la TM M = ({q0, q1, q2, qf}, {0, 1}, {0, 1, □}, δ, q0, □, {qf}), descrivere il suo linguaggio.
La TM è la seguente:
L(M) = il linguaggio regolare 01*
Definire una TM che converta un numero intero binario in decimale.
Esempio:
- 000 --> 0
- blank --> 0
- 1001 --> 9
La macchina N è così definita:
N = ({q0, q1, q2, ..., q11}, {0, 1}, {0, 1, □, X, 1, 2, 3, 4, 5, 6, 7, 8, 9}, δ, q0, □, {q11})
Definire una TM che accetti stringhe binarie palindrome.
È sufficiente modificare l'esercizio 8.2.2.c del tutorato 8, che accettava i palidromi pari. Infatti sono state aggiunte solo le due transizioni da q3 e q5 verso lo stato accettante q6, che considerano il caso in cui la stringa sul nastro abbia lunghezza dispari.
T = ({q0, q1, q2, q3, q4, q5, q6}, {0, 1}, {0, 1, X, □}, δ, q0, □, {q6})
Definire una TM che accetta L = {1n0m1m-1 | n ≥ 0, m > 0}
T = ({q0, q1, q2, q3, q4, q5}, {0, 1}, {0, 1, X, Y, □}, δ, q0, □, {q5})
