ESAME DI LINGUAGGI E TRADUTTORI

ESAME DI LINGUAGGI E TRADUTTORI

22 Giugno 1999

Esercizio 1

1. Scrivere una grammatica che generi ed un automa che riconosca il linguaggio

L= { aⁿ a^m b^q a^s c^t| s-t>n-m, t<=s+q, n, m, s, t >=0}

Consideriamo i due casi:

1) n + m = 2k con k>= 0 (cioè è pari) : al fine di massimizzare il numero di casi in cui il vincolo

s – t > n – m, poniamo

n = k

m = k

ciò implica che n – m = 0 e quindi otteniamo:

L=L1={(aa)^* b^* a^s c^t | s – t >0, t <= s+q, s,t >= 0}

Possiamo semplificare ulteriormente:

s-t > 0 => s > t => s+q >= t

e infine:

L1={(aa)^* b^* a^s c^t | s > t >= 0} = {(aa)^* b^* a^t a⁺c^t | t >= 0 }

2) n + m = 2k + 1 con k>= 0 (cioè è dispari) : al fine di massimizzare il numero di casi il vincolo

s – t > n – m, poniamo

1. n = k + 1

2. m = k

cio implica che n – m = 1 e quindi otteniamo:

L=L2={(aa)^*a b^q a^s c^t | s – t > 1, t <= s+q, s,t >= 0}

Possiamo semplificare ulteriormente:

s > t + 1 => s+q >= t

e infine:

L2={(aa)^*a b* a^ta a^tc^t | t >= 0}

L = L1È L2

La grammatica è la seguente:

S ® L₁ | L₂

L_{1 ®} A^’ B L₁

L₁^’® aL₁^’c | aA

A ® aA | e

B ® bB | e

A^’ ® aaA | e

L_{2 ®} A^’aB L^’₂

L^’_2® aL^’₂c | aaA

Di seguito è riportata la rappresentazione dell’ automa non deterministico a pila

L = L1È L2

L1={(aa)^* b^* a^t a⁺c^t | t >= 0 }

L2={(aa)^*a b* a^ta a^tc^t | t >= 0}

AUTOMA A PILA NON DETERMINISTICO

Gli stati q₄-q₅ sono equivalenti a q₁₀-q₁₁.

AUTOMA A PILA DETERMINISTICO

L’automa inserisce tutte le a che trova sin dall’inizio nella PILA. Se trova una b, "azzera" la pila inserendo un simbolo marcatore (si è usato Z per semplificare la scrittura dell’automa, ma si poteva utilizzare un altro simbolo complicando un po’ la cosa ), altrimenti se trova c, verifica la condizione che il numero di a superi di 1 o 2 unità il numero di c, a seconda se le a sono pari o dispari.

2. Scrivere un parser discendente per il linguaggio definito dalla grammatica le cui produzioni sono di seguito riportate:

RISOLUZIONE :

INSIEMI FIRST :

FIRST(S ) = { a, g, h }

FIRST(S’) = { b, a, h, s }

FIRST(A ) = { a }

FIRST(A’) = { a, z, b }

FIRST(B ) = { b,e }

FIRST(C ) = { a, h }

FIRST(D ) = { g, e }

FIRST(E ) = { s }

FIRST(E’) = { z, b }

FIRST(F ) = { s, z }

FIRST(G ) = { s }

FIRST(G’) = { a, b, s, z }

FIRST(H ) = { z }

FIRST(H’) = { g, e }

FIRST(L ) = { b }

FIRST(L’) = { g, e }

INSIEMI FOLLOWS :

FOLLOWS(S ) = { $ }

FOLLOWS(S’) = { $ }

FOLLOWS(A ) = { a, b, d, h, s }

FOLLOWS(A’) = { a, b, d, h, s }

FOLLOWS(B ) = { a, h, d, f }

FOLLOWS(C ) = { $, z, u }

FOLLOWS(D ) = { a, h }

FOLLOWS(E ) = { $, z }

FOLLOWS(E’) = { $, z }

FOLLOWS(F ) = { u, d }

FOLLOWS(G ) = { d }

FOLLOWS(G’) = { d }

FOLLOWS(H ) = { $, d }

FOLLOWS(H’) = { $, d }

FOLLOWS(L ) = { d, t }

FOLLOWS(L’) = { d, t }

V_T= { a, b, d, f, g, h, s, t, u, z, $ }

| V_T | = 11

V_N= { S, S’, A, A’, B, C, D, E, E’, F, G, G’, H, H’, L, L’ }

| V_N | = 16

L’unico conflitto nella tabella di parsing è per la regola

S ® AS’ | DCH

Quando D ® e, infatti :

E fattorizzando :

S ® aS’’ | gDCH | hGdH

S’’ ® A’S’ | CuH

Il problema si ripropone in quanto A’® Ad .

TABELLA DI PARSING

Esercizio 2

Una matrice M di bit n ×m, si dice matrice C-Grey se, per ogni j=1,m-1, la j-esima colonna della matrice differisce dalla colonna (j+1)-esima esattamente in un bit. Si realizzi un programma Prolog che, data M rappresentata come lista di righe, risponda si se M e’ C-Grey.

RISOLUZIONE :

cgrey(L1, L2) :- cgrey(L1, L2, 0).

cgrey([], [], 1).

cgrey([0 | L1], [0 | L2], X) :- cgrey(L1, L2, X).

cgrey([1 | L1], [1 | L2], X) :- cgrey(L1, L2, X).

cgrey([0 | L1], [1 | L2], 0) :- cgrey(L1, L2, 1).

cgrey([1 | L1], [0 | L2], 0) :- cgrey(L1, L2, 1).

col([], [], []).

col([[X | R] | M], [X | C], [R | M1]) :- col(M, C, M1).

trasp([[] | _]).

trasp(M, [C |M1]) :- col(M, C, M2), trasp(M2, M1).

iscgrey(M) :- trasp(M, M1), iscgrey1(M).

iscgrey1([R1, R2 | M]) :- cgrey(R1, R2), iscgrey1([R2 | M]).

iscgrey1([R]).

Sia data una matrice M n ×n di alberi binari in cui ogni elemento e’ un albero binario di interi. In particolare, le righe di ordine pari contengono alberi binari di ricerca, mentre quelle di ordine dispari contengono alberi binari qualsiasi. Si scriva un programma Prolog Statistica(M,A) che, data M, restituisca una matrice A di interi della stessa dimensione di M e tale che A[i,j] sia posto uguale al numero di occorrenze dell’intero (i+j) nell’albero binario M[i,j].

RISOLUZIONE :

statistica(M, A) :- stat(M, 1, A).

stat([], _, []).

stat([R | M], I, [RA | A]) :- stat1(R, I, 1, RA), I1 is I + 1, stat(M, I1, A).

stat1([], _, []).

stat1([ALB | L], I, J, [C1 | C]) :- Z is I + J, X is (I mod 2), conta(ALB, Z, X, C1), J1 is J + 1,

stat1(L, I, J1, C).

conta(ALB, Z, 0, C1) :- contabil(ALB, Z, C1).

conta(ALB, Z, 1, C1) :- contatutti(ALB, Z, C1).

contatutti(nil, _, 0).

contatutti(alb2(X, FD, FS), Z, C) :- contatutti(FD, Z, C1), contatutti(FS, Z, C2),

contare(X, Z, C3), C is C1 + C2 + C3.

contare(Z , Z, 1) :- !.

contare(_ , _, 0).

contabil(alb2(Z, alb2(Z, FD, FS), _), Z, C) :- !, contabil(alb2(Z, FD, FS), Z, C1), C is C1 + 1.

contabil(alb2(Z, FD, FS), Z, 1) :- !.

contabil(nil, _, 0).

contabil(alb2(X, FD, FS), Z, C) :- Z > X, !, contabil(FS, Z, C).

contabil(alb2(X, FD, FS), Z, C) :- contabil(FD, Z, C).

Esercizio 3

1. Scrivere una macchina di Turing che riconosca il linguaggio:

L = {an bn2 + n | n > 0}

Gli stati da 0 a 2 copiano le a su (1) e (2)

Quando si passa in q3 viene aggiuta una a in più su (1) (n²+n = n(n+1))

Gli stati 3-6 effettuano il prodotto tra (1) e (2) in unario (ogni a è un "1")

Negli stati 3 e 5, se (2) è stato scandito interamente e così anche le b in (I), la stringa è accettata

2. Verificare se la seguente grammatica e’ SLR(1) :

S ® Sa | cAb | e

A ® Aa | Bc | e

B ® cSb | d

RISOLUZIONE :

S ® Sa

S ® cAb

S ® e

A ® Aa

A ® Bc

A ® e

B ® cSb

B® d

Tabella analisi ascendente SLR(1)