Calcolabilit`a e linguaggi formali 4 Settembre 2013

Calcolabilit` a e linguaggi formali

4 Settembre 2013

Domanda 1

(a) Dare una grammatica per ciascuno dei seguenti linguaggi:

L1= {(aⁿa)^mba^k: k ≥ 0, n > 1, 1 < m < 4};

L₂= {aⁿ(a^mb)a^k: k ≥ 0, n = 2, m = k}.

(b) Determinare il tipo della grammatica data nella classificazione di Chomsky.

(c) Determinare il tipo del linguaggio. Se il linguaggio `e di tipo 3, dare un’espressione regolare o un automa finito corrispondente. Se il linguaggio `e di tipo 2 dimostrare tramite il pumping lemma tipo 3 che non `e un linguaggio regolare.

Soluzione

(a) Semplifichiamo la descrizione di L₁.

L₁= {(aⁿa)^mba^k: k ≥ 0, n > 1, 1 < m < 4} =

= {(aⁿ⁺¹)^mba^k: k ≥ 0, n > 1, m ∈ {2, 3}} =

= {a²⁽ⁿ⁺¹⁾ba^k : k ≥ 0, n > 1} + {a³⁽ⁿ⁺¹⁾ba^k: k ≥ 0, n > 1} =

= {a^2hba^k : k ≥ 0, h > 2} + {a^3hba^k : k ≥ 0, h > 2}.

Diamo una grammatica per L₁. Le produzioni sono:

S → AbB|CbB, A → aaA|a⁶, B → aB|, C → aaaC|a⁹. Semplifichiamo la descrizione di L2.

L2= {aⁿ(a^mb)a^k: m, k ≥ 0, n = 2, m = k} = {aaa^mba^m: m ≥ 0}.

Diamo una grammatica per L2. Le produzioni sono:

S → aaX, X → aXa|b.

(b) Entrambe le grammatiche sono libere da contesto (tipo 2).

(c) L1 ´e un linguaggio regolare (tipo 3).

Una espressione regolare corrispondente ´e la seguente:

a⁶(aa)^∗ba^∗+ a⁹(aaa)^∗ba^∗.

L₂ ´e un linguaggio libero da contesto (tipo 2).

Applichiamo il pumping lemma tipo 3 per dimostrare che non ´e un linguaggio regolare.

Per ogni n naturale, consideriamo la stringa x = aⁿ⁺²baⁿ, x appartiene ad L e |x| ≥ n.

Ogni scomposizione di x in tre parti, x = uvw, con |uv| ≤ n e |v| = r ≥ 1 ´e tale che v ´e in a⁺, quindi pompando i volte v, con i = 0, otteniamo uw = a^n+2−rbaⁿ che non appartiene ad L. CVD

Domanda 2

(a) Definire induttivamente le espressioni regolari (suggerimento: sono necessari 6 casi).

(b) Associare un automa finito ad ogni caso della definizione induttiva di espressione regolare