Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
Algoritmi e Principi dell'Informatica Appello d esame 17 luglio 2014 svolgere tutti gli esercizi in 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1, 2 e 3 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 4 e 5 in 1 ora e 15 minuti. cativo. Esercizio 1a (punti 5) e L(A) definiti da G: S | a S b A: a, Z0/Z0C a, A/AA b, A/ b, A/ b, B/BB b, Z0/Z0B a, B/BB a, A/B aC/CB a, B/BB b, B/BB b, C/ b, C/ a, Z0/Z0B b, Z0/Z0B a, C/CA Si costruiscano un automa o una grammatica a potenza minima che riconoscano/generino rispettivamente L(G) L(A) e L(G) L(A). Nome:_____________________________________ Matricola:_________________________________ Firma:_____________________________________ L(G) è chiaramente il linguaggio {anbn | n 0} A invece accetta tutte le stringhe non in L(G) oltre la stringa nulla. Quindi L(G) L(A) = {a, b}* e L(G) L(A = { }, entrambi linguaggi regolari. Esercizio 2 (punti 6) Si consideri la seguente formula F: x y ( z m(x,y,z) t m(x,y,t) ) 2.a Come noto, una formula può essere intesa in senso puramente sintattico come una sequenza di simboli. Si indichi la categoria sintattica (funzione, predicato, ecc.) di ciascun simbolo utilizzato in F; se pertinente, indicare anche la arietà associata al simbolo. Si dica anche se F è una formula chiusa. quantificatore universale x variabile z variabile quantificatore esistenziale y variabile m predicato con arietà 3 ( punteggiatura , punteggiatura ) punteggiatura connettivo logico (implicazione) t variabile La formula è chiusa in quanto tutte le variabili sono quantificate. 2.b con indice y e ingresso x produce z in uscita. Motivare la risposta. Se, data una coppia di valori <x,y>, esiste un valore z tale che <x,y,z>…
First page of the document.
