Esercizio pumping lemma

Esercizio pumping lemma

Dato il linguaggio, stabilire il suo tipo e definire una grammatica G tale che L(G) = L*

L = {aⁿbⁿc^k | n, k ∈ N}

Sia G una grammatica tale che L(G) = L

G = (X,V,S,P) con X = {a,b,c} e V = {S,A,C}

P = {

S -> AC
A -> aAb | ϵ
C -> cC | ϵ

}

L è almeno di tipo 2 perchè generato da una grammatica libera da contesto.

Supponiamo per assurdo che L sia regolare, quindi vale il pumping lemma per i linguaggi regolari. Per il pumping lemma:

∃p ∈ N tale che ∀z ∈ L, |z| >= p

allora

z = uvw con

1) |uv| <= p
2) |v| > 0
3) uvⁱw∈ L, ∀i >= 0

Consideriamo

z = uvw = a^pb^p ∈ L, |z| = p + p >= p  quindi per il pumping lemma  z = uvw

v può essere così composta:

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

v non può essere composta da sole b o a cavallo tra le a e le b perchè risulterebbe |uv| > p e non è ammesso dal pumping lemma.

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

Consideriamo la stringa gonfiata uv²w

uv²w = a^p-j (a^j)² b^p = a^p-j b^2j b^p = a^p+j b^p

uv²w ∉ L

Per assurdo L non è un linguaggio regolare, L è al più di tipo 2