ESAME DI LINGUAGGI E TRADUTTORI

25 Febbraio 2000 - Parte I (2 ore)

Esercizio 1

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

L = { b⁺ aⁿ b^m c^q (a^s | c^r) a^* | r > 0 ,s >=0 , n > r, n > s, n+m < q, m>1}

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

S ®SdSd |A ;

A ®EG = B

B ®CtCeC | C

C ®D | B

D ®EG| E | F

E ®aE | b

F ®bF | b

G ®( ) | ( D!H )

H ®D!H | D

ESAME DI LINGUAGGI E TRADUTTORI

25 Febbraio 2000 - Parte II (2 ore)

Esercizio 2

Sia dato un grafo orientato contenente n nodi ed m archi rappresentato con fatti del tipo

nodo(i)

arco(k,i,j)

dove k indica il numero pregressivo dell’arco, i il nodo di partenza e j il nodo di arrivo.

1. Scrivere un programma Prolog che alla interrogazione

?- camminodispari(L)

restituisca la lista delle coppie (i,j) di nodi per cui esiste un cammino da i a j di lunghezza dispari.

2. Scrivere un programma Prolog che alla interrogazione

?-matriceIncidenza(L)

restituisca la matrice di incidenza n ×m del grafo rappresentata attraverso una lista L di righe. La matrice di incidenza di un grafo e’ definita nel seguente modo. Le righe R1, ..., Rn sono ordinate a partire dal primo nodo. Ogni riga Ri e’ una lista di lunghezza m contenente solo i valori 0,1,-1. L’elemento di posto k vale 1 se i e’ il nodo da cui esce l’arco k, vale -1 se i e’ il nodo in cui termina l’arco k e vale zero altrimenti.

Esercizio 3

1. Scrivere una macchina di Turing che legge sul nastro di input due stringhe x e y separate da spazio bianco e stampi sul nastro di output la stringa y da cui sono state eliminate tutte le eventuali sottostringhe xx. Ad esempio, se x = ’ab’ e y = ’cababbababc’, va stampato ’cbc’.

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

S ®SbA | a

A ®cAb | cB

B ®aS | e