Calcolabilit` a e Linguaggi Formali Parte II Compito AAAAA
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= {anbmc2n : n, m > 0};
L2= {anbk+nch: 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.
Soluzione
Una grammatica libera per L1: S ::= aScc|aBcc
B ::= b|bB
Il linguaggio L1 non e’ regolare. Supponiamo per assurdo che lo sia. Sia n > 0 il numero di stati di un automa che riconosce L1. Consideriamo la stringa anbc2n. Siccome 2n > n, possiamo dividere c2n in tre sottostinghe c2n = xyz con y 6= in maniera tale che anbxz appartiene ancora al linguaggio L1. Ma in questo caso si perde la simmetria tra il numero di a ed il numero di c, perche’ xz = crcon r < 2n. Assurdo.
Si ha L2= {anbnb2rc : n, r > 0} ∪ {anbnb2rcc : n, r > 0}. Ecco una grammatica libera per L2: S ::= ABc|ABcc
A ::= aAb|ab B ::= bb|bbB
Il linguaggio L2 non e’ regolare. Supponiamo per assurdo che lo sia. Sia n > 0 il numero di stati di un automa che riconosce L2. Consideriamo la stringa anbnbbc. Siccome n + 2 > n, possiamo dividere bn+2 in tre sottostinghe bn+2 = xyz con y 6= in maniera tale che anxzc appartiene ancora al linguaggio L2. Ma in questo caso si perde la simmetria tra il numero di a ed il numero di b, perche’ xz = brcon r < n + 2. Assurdo.
Esercizio 4
Semplificare la seguente espressione regolare giustificando ogni passaggio:
(R + RS∗+ ∗S∗)∗+ (U + SR∗)∗
Soluzione
Definiamo per brevit`a Z = (R + R∗S + ∗S∗)∗+ (U + SR∗)∗.
Prima di tutto ∗= {}. Siccome ∈ S∗ allora possiamo semplificare ∗S∗ con S∗ ed otteniamo Z = (R + S)∗+ (U + SR∗)∗
Inoltre, (R + R∗S + S∗)∗= (R + R∗S + S)∗ e R∗S ⊆ (R + S)∗ da cui otteniamo Z = (R + S)∗+ (U + SR∗)∗