06 07 2015

Page 1

Algoritmi e Prin Informatica Appello del 6 Luglio 2015 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singol i esercizi hanno senso solo con hanno valore puramente indicativo. Esercizio 1 (punti 9) Punto a) = {(, ),]}, tali che le parentesi tonde s iano bilanciate ossia ben parentetizzate , con la variante che la parentesi quadra può bilanciare un numero arbitrario (non nullo) di parentesi tonde aperte. Ad esempio, le stringhe (()()), ((())), ((()(](()] ap partengono al linguaggio, mentre le stringhe ((), ((((](, ]()() non vi appartengono. Si scriva una grammatica , preferibilmente a potenza minima che produca il linguaggio L1. In alternativa è possibile costruire un automa, sempre a potenza minima, che rico nosca lo stesso linguaggio; ciò però comporta una diminuzione del punteggio ottenibile di 2 punti. Punto b) E' vero che se un linguaggio L non è regolare allora neanche il suo complemento L c è regolare? Perché? Punto c) E' vero che se un linguaggio L non è libero dal contesto allora neanche il suo complemento L c è libero dal contesto? Perché? Esercizio 2 (punti 7) Si consideri l proprietà, che indica che il suo argomento appartiene al sottoinsieme di S costituito da stringhe in cui non compaiano due caratteri consecutivi appartenenti ad A1. Ad esempio, se i caratteri di A1 sono lettere maiuscole e quelli di A2 lettere minuscole, le seguenti stringhe soddisfano la proprietà suddetta: AbcDghm, cvHmUnI, mentre le seguenti non la soddisfano: NB: La formula deve far uso esclusivamente dei simboli seguenti: Quantificatori e connettivi logici proposizionali…