Linguaggi di programmazione: esercizio 1 pumping lemma

Esercizio pumping lemma

Dimostrare se questo linguaggio non è libero da contesto:

L = {0ⁿ 1^m | m >= 0, n = m²}

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 la parola: z = 0^(p+1)2 1^(p+1)

z ∈ L, |z| = (p+1)² + p+1 > 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

|uv²wx²y| = |uvwxy| + |vx| <= |uvwxy| + |vwx| <= (p+1)² + p + 1 + p <= p² + 2p + 1 + p + 1 + p = p² + 4p + 2 < (p+2)² + p + 1 + p = p² + 4p + 4 + p + 2 = p² + 5p + 6

Quindi, p² + 4p + 2 < p² + 5p + 6

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.