Calcolabilit` a e Linguaggi Formali Parte II Compito BBBBB

Calcolabilit` a e Linguaggi Formali Parte II Compito BBBBB

16 Dicembre 2014

Esercizio 1

Enunciare e dimostrare il secondo teorema di ricorsione.

Soluzione

Teorema. Sia h una funzione calcolabile totale. Allora esiste un numero naturale n tale che φn= φ_h(n).

Prova. Si definisca la seguente funzione di due variabili:

f (x, y) = φ_h(φx(x))(y).

f `e calcolabile:

Input x,y;

Decodifica x per ottenere il programma Px; If Px↓ x then z := h(φx(x));

Decodifica z per ottenere il programma Pz; If Pz↓ y then Output φz(y).

Possiamo applicare il teorema del parametro. Esiste una funzione calcolabile totale s tale che φ_s(x)(y) = f (x, y).

Sia m un indice tale che s = φm. Allora abbiamo

φ_s(x)(y) = φ_φm(x)(y) = φ_h(φx(x))(y) ed assegnando il valore m ad x si ha:

φ_s(m)(y) = φ_φm(m)(y) = φ_h(φm(m))(y)

Si noti che essendo s ed h funzioni totali, φ_m(m) e h(φ_m(m)) sono ben definiti. Per ottenere la conclusione, bisogna definire n = φ_m(m).

Esercizio 2

Dimostrare che K = {x : Px↓ x} non `e estensionale (i.e., non rispetta le funzioni).

Soluzione

Sia n un indice di un programma che si autoriconosce. In altre parole, Pn ↓ n, mentre Pn ↑ x per ogni x 6= n. Sia inoltre r 6= n tale che φn= φr. Si vede facilmente che n ∈ K mentre r /∈ K. Infatti Pr↑ r perch´e Pr converge solo su n ed r 6= n.

Esercizio 3

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

L1= {(aⁿb)^mca^k: n, m, k > 0};

L2= {aⁿb^k+nc^h: n, k, h > 0, k pari, 1 ≤ h ≤ 2}.

(b) Determinare il tipo di grammatica data nella classificazione di Chomski;

(c) Determinare il tipo del linguaggio. Se il linguaggio non `e regolare verificarlo con il pumping lemma. Se il linguaggio

`e regolare definire un’espressione regolare che lo definisce.

Soluzione

Il linguaggio L₁ = {(aⁿb)^mca^k : n, m, k > 0} non `e n`e regolare n`e libero. Infatti il tipo di simmetria della stringa (aⁿb)^m= aⁿbaⁿb . . . aⁿb (m volte) richiede della memoria per ricordarsi il numero n. Quindi il linguaggio puo’ essere generato da una grammatica di tipo 0.

Il linguaggio L2`e libero dal contesto. Possiamo scrivere

L2= {aⁿbⁿb^2rc : n, r > 0} ∪ {aⁿbⁿb^2rcc : n, r > 0}

Una grammatica che genera L2: S ::= ABc|ABcc

Utilizziamo il simbolo nonterminale A per generare il linguaggio {aⁿbⁿ : n > 0}, ed il simbolo nonterminale B per generare il linguaggio {b^2r: r > 0}.

A ::= aAb|ab B ::= bb|bbB

Supponiamo per assurdo che il linguaggio L₂sia regolare. Supponiamo che siano n gli stati di un automa che riconosce L₂. Consideriamo la stringa

aⁿbⁿbbc

Il numero di b `e pi`u grande di n. Allora esiste una suddivisione di bⁿ⁺²= xyz in tre parti con y 6=  in maniera tale che xz = b^s con s < n + 2. Si perde la simmetria tra aⁿ e bⁿbb. Infatti l’automa riconosce

aⁿxzc = aⁿb^sc ed s < n + 2.

Esercizio 4

Semplificare la seguente espressione regolare giustificando ogni passaggio:

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

Soluzione

Definiamo per brevit`a Z = (R + S^∗R + ^∗U^∗)^∗+ (S + SR^∗)^∗.

Prima di tutto ^∗= {}. Siccome  ∈ U^∗allora possiamo semplificare ^∗U^∗ con U^∗ ed otteniamo Z = (R + S^∗R + U^∗)^∗+ (S + SR^∗)^∗

Inoltre, S ⊆ SR^∗ e R ⊆ S^∗R perch´e

SR^∗= S + SR + SRR + · · · + SRⁿ+ . . . e

S^∗R = R + SR + SSR + · · · + SⁿR + . . . Quindi otteniamo

Z = (S^∗R + U^∗)^∗+ (SR^∗)^∗ By U^∗∗= U^∗ we derive

Z = (S^∗R + U )^∗+ (SR^∗)^∗ Attenzione! Z 6= (S + R + U )^∗ perch´e per esempio SU 6⊆ Z.