Linguaggi di programmazione – esercizio 2 pumping lemma

Esercizio pumping lemma

Dimostrare se questo linguaggio sia libero da contesto:

L = {aⁱ b^j c^k | i,j,k ≥ 0, j = max(i,k)}

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 = a^rb^rc^r con r = p+1
z ∈ L, |z| = 3r > p quindi per il pumping lemma z = uvwxy

Per la 1) del Pumping Lemma si hanno le seguenti possibilità:

1) vwx è costituita da sole a: vwx = a^k con 0<k≤p

2) vwx è costituita da sole b: vwx = b^k con 0<k≤p

3) vwx è costituita da sole c: vwx = c^k con 0<k≤p

4) vwx è a cavallo tra le a e le b: vwx = a^kb^y con 0<k+y≤p

5) vwx è a cavallo tra le b e le c: vwx = b^kc^y con 0<k+y≤p

vwx non può essere contemporaneamente a cavalo tra a,b e c perché sarebbe troppo lunga: |vwx| > p

Analizziamo ciascun caso:

1) Consideriamo la stringa pompata uv²wx²y
aggiungiamo almeno una a ed al più p  a

uv²wx²y = a^r+t b^r c^r con 0<t≤p

uv²wx²y ∉ L perché #(b) ≠ max(#a, #c)

 

2) Consideriamo la stringa pompata uv²wx²y
aggiungiamo almeno una b ed al più p  b

uv²wx²y = a^r b^r+t c^r con 0<t≤p

uv²wx²y ∉ L perché #(b) ≠ max(#a, #b)

 

3) Consideriamo la stringa pompata uv²wx²y
aggiungiamo almeno una c ed al più p  c

uv²wx²y = a^r b^r c^r+t con 0<t≤p

uv²wx²y ∉ L perché #(b) ≠ max(#a, #c)

 

4) Per la 2) del Pumping Lemma si distinguono i seguenti casi:

• 4a) v ≠ ɛ, x ≠ ɛ
• 4b) v ≠ ɛ, x = ɛ
• 4c) v = ɛ, x ≠ ɛ

 

4a) v ≠ ɛ, x ≠ ɛ allora v = a^k1 con 0<k¹≤k e x = b^y1 con 0<y1≤y
consideriamo la stringa spompata uv⁰wx⁰y

uv⁰wx⁰y = a^r-k1 b^r-y1 c^r

uv⁰wx⁰y ∉ L perché #(b) ≠ max(#a, #c)

 

4b) v ≠ ɛ, x = ɛ allora v = a^k1 con 0<k¹≤k
consideriamo la stringa pompata uv²wx²y

uv²wx²y = a^r+k1 b^r c^r

uv²wx²y ∉ L perché #(b) ≠ max(#a, #c)

 

4c) v = ɛ, x ≠ ɛ allora x = b^y1 con 0<y¹≤y
consideriamo la stringa pompata uv²wx²y

uv²wx²y = a^r b^r c^r+y1

uv²wx²y ∉ L perché #(b) ≠ max(#a, #c)

 

5) Per la 2) del Pumping Lemma si distinguono i seguenti casi:

• 5a) v ≠ ɛ, x ≠ ɛ
• 5b) v ≠ ɛ, x = ɛ
• 5c) v = ɛ, x ≠ ɛ

 

5a) v ≠ ɛ, x ≠ ɛ allora v = b^k1 con 0<k¹≤k e x = b^y1 con 0<y¹≤y
consideriamo la stringa spompata uv⁰wx⁰y

uv⁰wx⁰y = a^r b^r-k1 c^r-y1

uv⁰wx⁰y ∉ L perché #(b) ≠ max(#a, #b)

 

5b) v ≠ ɛ, x = ɛ allora v = b^k1 con 0<k¹≤k
consideriamo la stringa pompata uv²wx²y

uv²wx²y = a^r b^r+k1 c^r

uv²wx²y ∉ L perché #(b) ≠ max(#a, #c)

 

5c) v = ɛ, x ≠ ɛ allora x = c^y1 con 0<y¹≤y
consideriamo la stringa pompata uv²wx²y

uv²wx²y = a^r b^r c^r+y1

uv²wx²y ∉ L perché #(b) ≠ max(#a, #c)

 

Analizzando tutti i casi la stinga spompata e pompata non appartiene ad L.
Per assurdo ne consegue che L non è libero da contesto.