Esercizio pumping lemma

Esercizio pumping lemma

Dimostrare se questo linguaggio non è libero da contesto:

L = {a^{n^2} | n >= 0}

Supponiamo per assurdo che L sia libero da contesto, quindi vale il pumping lemma per i linguaggi liberi da contesto. Per il pumping lemma:

∃p ∈ N, p dipendente solo da L, tale che se z ∈ L, |z| > p

allora

z = uvwxy con

1) |vwx| <= p
2) vx ≠ ϵ
3) uvⁱwxⁱy ∈ L, ∀i >= 0

Consideriamo

z = uvwxy = a^{p^2} ∈ L, |z| = p² > p  quindi per il pumping lemma  z = uvwxy

Consideriamo la stringa uv²wx²y
Per la (3) del pumping lemma uv²wx²y ∈ L, ma osserviamo la catena di maggiorazioni

|uv²wx²y| = |uvwxy| + |vx| <= p² + p < p² + 2p + 1 = (p + 1)²

Quindi, |uv²wx²y| < (p + 1)²

Inoltre |uv²wx²y| > |uvwxy| perché per la (2) del pumping lemma vx ≠ ϵ

Per assurdo ne consegue che uv²wx²y ∉ L, quindi L non è libero da contesto.