21 02 2013

Pagina 1

Algoritmi e Principi dell’Informatica Appello del 21 Febbraio 2013 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 3 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1, 2, 3 in 1 ora e 30 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 4, 5, 6 e in 1 ora e 30 minuti. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Modulo I Esercizio 1 (punti 5) Si considerino i seguenti linguaggi L1 = 𝑎!!𝑏!!!𝑑 | 𝑘>0,1≤𝑗≤𝑘,𝑖!>0 = {abd, aabbabd, aabbaabbd, abaabbd, … abaaabbbabd, … aabbabaaabbbd, …} L2 = 𝑎!𝑏!!𝑐𝑎!!!𝑑 | ℎ>0,𝑘>0,1≤𝑗≤𝑘,𝑖!>0 = {abcad, … aaabbcaad, aaabbbcaaad, aabbbcaaabcad, …} 1. Definire una grammatica non contestuale che generi L1 e un automa a pila deterministico che lo accetti. 2. Definire una grammatica non contestuale che generi L2 e un automa a pila, preferibilmente deterministico, che lo accetti. 3. Definire una grammatica non contestuale che generi L1∪L2. Se possibile, definire un automa a pila deterministico che lo accetti; altrimenti argomentare in modo informale ma convincente che il linguaggio L1∪L2 non può essere accettato da un automa a pila deterministico, e definire un automa a pila nondeterministico che accetti L1∪L2. Esercizio 2 (punti 5) Si specifichi in logica del prim’ordine una funzione f : A* × N → A, dove A è un alfabeto di simboli e N è l’insieme dei numeri naturali, che, data una stringa costruita sull’alfabeto A e un numero i, restituisce il carattere in posizione (i+1)-esima nella stringa (cioè il carattere con indice i nella stringa, dove 0 è l’indice del primo carattere, 1 del secondo, e così via). Nella specifica, è consentito l’uso delle seguenti…