Linguaggi di programmazione – esercizio 3 pumping lemma

Esercizio pumping lemma

Determinare il tipo del linguaggio:

L_ab = {w ∈ {a,b}* | n_a(w) = n_b(w)}

Per prima cosa dobbiamo trovare la grammatica così da identificare il tipo:

G = (X, V, S, P)
X = {a,b}
V = {S}

P = {
S -> ab | ba | SS | aSb | bSa | ε
}

Quindi L è almeno libero da contesto perché generato da una grammatica libera da contesto. Proseguiamo con la verifica se, questo linguaggio, può essere di tipo 3. Per assurdo supponiamo che L sia un linguaggio regolare. Se L è un linguaggio regolare allora per L vale il pumping lemma per i linguaggi regolari, quindi:

∃p ∈ N tale che ∀z ∈ L, |z| ≥ p allora z = uvw con

1) |uv| < p
2) |v| > 0
3) uv^tw ∈ L, ∀t ≥ 0

Consideriamo z = a^pb^p, z ∈ L  e |z| = 2p ≥ p quindi per il pumping lemma z = uvw

v può essere così composta:

• di sole a: v =a^j con 1 ≤ j ≤ p

z = uvw = a^p-j a^j b^p

Consideriamo la stringa pompata uv²w
uv²w = a^p-j (a^j)² b^p = a^p-j a^2j b^p = a^p+j b^p
uv²w ∉ L. Per assurdo L non è un linguaggio regolare, quindi è al massimo libero da contesto.