Linguaggi di programmazione – esercizio 1 proprietà di chiusura

Esercizio proprietà di chiusura

Dati i due linguaggi

L₁ = {0ⁿ 1ⁿ | n ≥ 0}
L₂ = {2^k | k ≥ 0}

Fornire una grammatica per L = L₁L₂ ∪ L₂L₁ e mostrare che è ambiguo.

Per prima cosa dobbiamo trovare le grammatiche dei due linguaggi:

• G₁ una grammatica tale che L(G₁) = L₁

G₁ = (X₁,V₁,S₁,P₁)
X₁ = {0,1}
V₁ = {S₁}

P₁ = {
S₁ -> 0S₁1 | ε
}

• G₂ una grammatica tale che L(G₂) = L₂

G₂ = (X₂,V₂,S₂,P₂)
X₂ = {2}
V₂ = {S₂}

P₂ = {
S₂ -> 2S₂ | ε
}

•  G₃ una grammatica tale che L(G₃) = L₁L₂

G₃ = (X₃,V₃,S₃,P₃)
X₃ = X₁ ∪ X₂ = {0,1,2}
V₃ = V₁ ∪ V₂ ∪ V₃ = {S₁, S₂, S₃}

P₃ = { S₃ -> S₁S₂ } ∪ P₁ ∪ P₂ =
P₃ = {
S₃ -> S₁S₂
S₁ -> 0S₁1 | ε
S₂ -> 2S₂ | ε
}

•  G₄ una grammatica tale che L(G₄) = L₂L₁

G₄ = (X₄,V₄,S₄,P₄)
X₄ = X₁ ∪ X₂ = {0,1,2}
V₄ = V₁ ∪ V₂ ∪ V₄ = {S₁, S₂, S₄}

P₄ = { S₄ -> S₂S₁ } ∪ P₂ ∪ P₁ =
P₄ = {
S₄ -> S₂S₁
S₂ -> 2S₂ | ε
S₁ -> 0S₁1 | ε
}

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

G = (X,V,S,P)
X = X₃ ∪ X₄ = {0,1,2}
V = V₃ ∪ V₄ ∪ S= {S, S₁, S₂, S₃, S₄}

P = { S -> S₃ | S₄ } ∪ P₃ ∪ P₄ =
P = {
S -> S₃ | S₄
S₃ -> S₁S₂
S₄ -> S₂S₁
S₁ -> 0S₁1 | ε
S₂ -> 2S₂ | ε
}

La grammatica G è ambigua perché vi sono almeno due alberi di derivazione differenti per derivare ad esempio la stringa 0011 ∈ L

Primo albero di derivazione per la stringa 0011

Secondo albero di derivazione per la stringa 0011