Calcolabilit` a e Linguaggi Formali Parte II Recupero II compitino

Calcolabilit` a e Linguaggi Formali Parte II Recupero II compitino

14 Gennaio 2015

Esercizio 1

Enunciare e dimostrare il secondo teorema di ricorsione.

Esercizio 2

Dimostrare il primo teorema di Rice applicando il secondo teorema di ricorsione.

Soluzione

Sia I 6= ∅, N un insieme che rispetti le funzioni. Supponiamo per assurdo che I sia decidibile. Si fissino due numeri c₀ ∈ I e c1 ∈ I. Si definisca allora la/ funzione f (x)= if x ∈ I allora f (x) = c₁ altrimenti f (x) = c₀. La funzione f e’ calcolabile totale in quanto I e’ decidibile. Dal secondo teorema di ricorsione esiste n tale che φ_n= φ_{f (n)}. Abbiamo due casi:

Se n ∈ I allora φn = φc₁ con c1 ∈ I. Quindi I non rispetta le funzioni./ Assurdo.

Se n /∈ I allora φn = φc₀ con c0 ∈ I. Quindi I non rispetta le funzioni.

Assurdo.

Esercizio 3

Determinare il tipo dei seguenti linguaggi:

L₁= {aⁿba^m+1a^m: n, m ≥ 0, m dispari};

L₂= {aⁿbaⁿ⁺¹a^m: n, m ≥ 0, 1 < m < 3}.

Se il linguaggio `e di tipo 3 definire una corrispondente grammatica regolare, un’espressione regolare ed un un automa a stati finiti.

Se il linguaggio `e di tipo 2 definire una grammatica libera da contesto o un automa a pila corrispondente e dimostrare tramite il pumping lemma di tipo 3 che non `e un linguaggio regolare.

Soluzione

Cominciamo con il linguaggio L₁. Se m = 1, 3, 5, . . . , e’ dispari, allora m = 2k+1 per k ≥ 0. Quindi sostituendo 2k + 1 per m si ottiene:

L₁= {aⁿba^m+1a^m: n, m ≥ 0, m dispari} = {aⁿba^2k+1+1a^2k+1: n, k ≥ 0}

da cui si ricava:

L1= {aⁿba^4k+3: n, k ≥ 0}.

Il linguaggio e’ regolare.

Espressione regolare: a^∗baaa(aaaa)^∗ Grammatica regolare:

S ::= aS|bB B ::= aB1

B1::= aB2

B₂::= aC C ::= |aC₁ C₁::= aC₂ C₂::= aC₃ C₃::= aC

Automa a stati finiti: insieme Q = {S, B, B1, B2, C, C1, C2, C3} di stati.

Stato iniziale: S. Unico stato finale C. Produzioni quelle della grammatica precedente. Per esempio, S →aS, etc.

Consideriamo il linguaggio L2. Si puo’ scrivere come segue (m = 2):

L2= {aⁿba³aⁿ: n ≥ 0}.

Il linguaggio e’ libero: S ::= aSa|baaa.

Dimostriamo ora che L2non e’ regolare. Supponiamo per assurdo che lo sia.

Esiste un numero naturale n > 0 tale che, se z ∈ L2 ha lunghezza maggiore di n, allora z puo’ essere scomposta in tre parti z = xyu con y 6=  in maniera tale che xyⁱu ∈ L₂ per ogni i ≥ 0. Inoltre la precedente scomposizione in tre parti esiste in ogni sottostringa di z che abbia lunghezza maggiore di n.

Si consideri quindi aⁿ⁺¹ba³aⁿ⁺¹. Allora esistono x, y, u con y 6=  tali che aⁿ⁺¹ba³aⁿ⁺¹ = xyuba³aⁿ⁺¹ ed inoltre xuba³aⁿ⁺¹ ∈ L₂. Questo e’ assurdo perche’ xu = a^k con k < n.

Esercizio 4

Semplificare le seguenti espressioni regolari giustificando ogni passaggio:

(a) ( + R^∗+ S^∗)^∗(U + R).

(b) (U S^∗+ R)^∗+ ((U + R^∗)^∗+ S)^∗.

2

Soluzione

(a)

( + R^∗+ S^∗)^∗(U + R) = (R^∗+ S^∗)^∗(U + R) perche’  + R^∗= R^∗

= (R + S)^∗(U + R) perche’ (R + S)^∗= (R^∗+ S^∗)^∗

= (R + S)^∗U + (R + S)^∗R (b)

(U S^∗+ R)^∗+ ((U + R^∗)^∗+ S)^∗ = (U S^∗+ R)^∗+ ((U + R)^∗+ S)^∗ perche’ (U + R^∗)^∗= (U + R)^∗

= (U S^∗+ R)^∗+ ((U + R) + S)^∗ perche’ ((U + R)^∗+ S)^∗= ((U + R) + S)^∗

= (U S^∗+ R)^∗+ (U + R + S)^∗

= (U + R + S)^∗ perche’ (U S^∗+ R)^∗⊆ (U + R + S)^∗

3