Linguaggi e Traduttori

Prof. Marco Gavanelli

14 giugno 2018

Esercizio 1 (punti 16)

Sia data una matrice A m×n che contiene solo valori 0 o 1. Si dice che essa è semi-connected-row-convex se, una volta eliminate le righe contenenti solo zeri, essa gode delle seguenti proprietà:

• row-convex: in ciascuna riga, gli 1 formano un intervallo, cioè non ci possono essere due 1 con in mezzo uno o più zeri. In altre parole, gli 1 sono tutti uniti: non è possibile che ci sia una sequenza (non vuota) di 1 seguita da una sequenza (non vuota) di 0, seguita da una sequenza (non vuota) di 1.
• connected: date due righe consecutive, A_i e A_i+1, ci deve essere almeno un 1 nella riga A_i e un 1 nella riga A_i+1 che sono connessi. Due 1 in posizione A_i,j e A_i+1,k sono connessi se j=k, j=k+1 oppure j=k−1. In altre parole, almeno un 1 nella riga i deve essere connesso (in verticale o in diagonale) con un 1 della riga i+1.

Ad esempio, la seguente matrice è semi-connected row-convex:

infatti, tolta la seconda riga (che è costituita solo da zeri), la matrice diventa:

La matrice:

non è semi-connected row-convex in quanto l'ultima riga non è convessa: ci sono due 1 separati da degli zero.

La matrice:

non è semi-connected row-convex in quanto le ultime due righe non sono connesse.

Si scriva una funzione Haskell

che verifica se una matrice (data come lista di liste di interi) gode della proprietà di essere semi-connected row-convex.

Ad esempio:

> scrc [[0,0,0],[0,1,0],[0,0,0],[1,1,1]]
True

Si usino opportunamente funzioni di ordine superiore.

Esercizio 1.1 (punti 1)

Una matrice si dice connected row-convex se le proprietà date nell'esercizio 1 valgono sia per le righe sia per le colonne.

Ad esempio, la matrice

è semi-connected row-convex, ma non è conected row-convex perché (anche togliendo la riga contenente solo zeri) l'ultima colonna non è convessa: ci sono due 1 separati da uno 0.

La matrice

invece è connected row-convex in quanto, una volta tolte le righe e le colonne contenenti solo 0, si ottiene:

che è connessa e row-convex sia nelle righe sia nelle colonne.

Si scriva una funzione

che verifica se una matrice è connected row-convex.

Esercizio 2 (punti 3)

Si scriva un programma Lex che verifica se una sequenza di 0 e 1 è convessa oppure no. Una sequenza è convessa se non ci sono mai due '1' intervallati da degli '0'.

Ogni sequenza di 0 e 1

• se è convessa deve essere visualizzata fra punti esclamativi
• se non è convessa deve essere stampata fra punti interrogativi.

Ad esempio:

100
!100!
011111100000
!011111100000!
10001
?10001?
100 000 101000 0001000
!100! !000! ?101000? !0001000!

Soluzione 1

scrc yss =
 let xss = filter not_all_zero yss
 in and (map row_convex xss) && all_connected xss

crc yss =
 let xss = filter not_all_zero yss
 tss = filter not_all_zero (trasposta xss)
 mss = trasposta tss
 in condition mss && condition tss

condition tss = and (map row_convex tss) && all_connected tss

not_all_zero ys = any (/=0) ys

row_convex xs = (dropWhile (==0).dropWhile (==1).dropWhile (==0)) xs == []

all_connected xss = and (zipWith connected xss (tail xss))

connected xs ys =
 (or (zipWith eq1 xs ys)) ||
 (or (zipWith eq1 (tail xs) ys)) ||
 (or (zipWith eq1 xs (tail ys)))

eq1 a b = (a==1) && (b==1)

trasposta ([]:_) = []
trasposta xss =
 map head xss:trasposta (map tail xss)

Altre soluzioni sono possibili. Ad esempio, invece di implementare la funzione trasposta era possibile usare la transpose.

Un altro modo per implementare la row_convex è eliminare i duplicati immediati e poi richiedere che la somma della lista sia al più 1 (ovvero, ci sia al più una sequenza di 1):

row_convex' xs =
 (sum.remdups) xs <= 1

remdups [x] = [x]
remdups [] = []
remdups (a:b:xs)
 | a==b      = remdups (b:xs)
 | otherwise = a:remdups (b:xs)

Oppure eliminare gli 0 all'inizio e alla fine della lista, poi richiedere che quello che rimane sia costituito solo da 1:

row_convex'' xs = (all (==1).dropWhile (==0).reverse.dropWhile (==0)) xs

Oppure si poteva notare che le righe convesse si possono descrivere con un linguaggio regolare (V. anche esercizio 2), quindi si poteva definire un automa a stati finiti (asf). In questo esempio, si usano 4 stati:

• Inizio: stato iniziale, fino ad ora sono arrivati solo 0
• Uno: finora si è vista una sequenza di 0 seguita da una sequenza di 1
• UnoZero: finora si è vista una sequenza di 0 seguita da una sequenza di 1, seguita da una sequenza di 0
• Errore: la stringa non è convessa

row_convex''' xs = (foldl asf Inizio xs) /= Errore

data Stati = Inizio | Uno | UnoZero | Errore deriving Eq
asf Inizio 0 = Inizio
asf Inizio 1 = Uno
asf Uno 1 = Uno
asf Uno 0 = UnoZero
asf UnoZero 0 = UnoZero
asf UnoZero 1 = Errore
asf Errore _ = Errore

Soluzione 2

CONV    0*1*0*
NONCONV (0|1)*

%%

{CONV}      printf("!%s!",yytext);
{NONCONV}   printf("?%s?",yytext);

%%