Esercizio svolto: tipo, grammatica, pumping lemma, L*

Esercizio svolto: tipo, grammatica, pumping lemma, L*

Dato il linguaggio

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

stabilire il tipo e generare una grammatica G tale che L(G) = L*
Ricavato L*, stabilire il tipo di linguaggio tra L*·L_B

L_B = {aⁿ b^m c^k | n ≤ m ≤ k}

 

Iniziamo col ricavare la grammatica di L, quindi L(G) = L

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

P = {
S -> AB
A -> ε | aAb
B -> ε | cB
}

L è libero da contesto, quindi tipo 2, perché generato da una grammatica libera da contesto.
Verifichiamo che L possa essere un linguaggio regolare (tipo 3).

Per assurdo supponiamo L regolare, quindi per L 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^tw ∈ L, ∀t ≥ 0

Consideriamo z = a^pb^p, z ∈ L  e |z| = p + p = 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.

 

Adesso possiamo ricavare una grammatica L(G₁) = L*

G₁ = (X₁, V₁, S₁, P₁)      X₁ = X = {a,b,c}       V₁ = V ∪ S₁ = {S₁, S, A, B}

P₁ = {
S₁ -> ε | SS₁
} ∪ P

P1 = {
S1 -> ε | SS₁
S -> AB
A -> ε | aAb
B -> ε | cB
}

Quindi L* è di tipo 2 perché la classe dei linguaggi liberi da contesto è chiusa rispetto all’operazione di iterazione.

Adesso ci rimane stabilire il tipo di linguaggio tra L*·L_B.

Iniziamo col ricavare la grammatica di L_B, quindi L(G₂) = L_B

G₂ = (X₂, V₂, S₂, P₂)      X₂ = {a,b,c}      V₂ = {S₂,B,C,D,E}

P₂ = {
S₂ -> aS₂BC | D
D -> BDC | E
EC -> CE
EB -> BE
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc
E -> ε | cE
}

Quindi L_B è un linguaggio dipendente dal contesto (tipo 1) perché generato da una grammatica contestuale.
Verifichiamo che L_B possa essere un linguaggio libero da contesto (tipo 2).

Supponiamo per assurdo che L_B 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^pb^pc^p
z ∈ L_B, |z| = p+p+p = 3p > 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_B

 

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_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_B

 

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^r e x = b^t con 0<r+t≤p
consideriamo la stringa pompata uv²wx²y

uv²wx²y = a^p+r b^p+t c^p

uv⁰wx⁰y ∉ L_B

 

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

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

uv²wx²y ∉ L_B

 

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

uv²wx²y = a^p b^p+t c^p

uv²wx²y ∉ L_B

 

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^r e x = c^t con 0<r+t≤p
consideriamo la stringa spompata uv⁰wx⁰y

uv⁰wx⁰y = a^p b^p-r c^p-t

uv⁰wx⁰y ∉ L_B

 

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

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

uv²wx²y ∉ L_B

 

5c) v = ɛ, x ≠ ɛ allora x = c^t con 0<t≤p
consideriamo la stringa spompata uv⁰wx⁰y

uv⁰wx⁰y = a^p b^p c^p-t

uv⁰wx⁰y ∉ L_B

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

L’ = L*·L_B

L’ è un linguaggio dipendete dal contesto perché per il teorema delle proprietà di chiusura, la concatenazione di un linguaggio libero da contesto (L*) e un linguaggio dipendente da contesto (L_B) genera un linguaggio dipendente da contesto (tipo 1).