15 11 2010 1

Pagina 1

Algoritmi e Principi dell'Informatica Prima prova in itinere - 15 Novembre 2010 Tempo a disposizione: 1h30’ Esercizio 1 (8 punti) Si scriva un automa (a stati finiti, a pila, macchi na di Turing oppure rete di Petri) che riconosce il linguaggio L fatto di tutte e sole le stringhe della forma a n1 bn2 cn3 in cui 0 < n1 < n2 < n3. NB : verranno dati 2 ulteriori punti di bonus in caso di modello a potenza minima . Esercizio 2 (11 punti) Formalizzare mediante formule di logica del prim'ordine le seguenti affermazioni: 2.1. L'insieme dei numeri naturali primi è illimitato. 2.2. C'è una infinità di macchine di Turing che calcolano funzioni totali. 2.3. Esistono macchine di Turing che calcolano funzioni con dominio finito. Si indichi come al solito con la funzione a due arg omenti f y(x) il valore calcolato dalla y-esima TM con ingresso x. Esercizio 3 (11 punti) Il professor Rice dà ai suoi studenti il seguente esercizio: “Scrivere un automa (a stati finiti, a pila, o macch ina di Turing) che riconosca il linguaggio L(G) generato dalla seguente grammatica G: S → ABCS | cABCABC ABC → a | b | c L'automa scritto deve essere a potenza riconoscitiv a minima tra quelli che riconoscono L(G), o la soluzione proposta sarà considerata sbagliata, e riceverà 0 punti. ” 3.1. E' decidibile il problema di stabilire se uno stude nte, in risposta all'esercizio, scrive una macchina di Turing, un automa a pila, o un automa a stati finiti? 3.2. E' possibile scrivere un programma che faccia in au tomatico la correzione delle soluzioni proposte dagli studenti, e cioè che, data una qualu nque soluzione proposta, dica se essa è corretta oppure no? Suggerimento: si individui il tipo di automa a pote nza riconoscitiva minima che risolve l’esercizio del professor Rice. Soluzioni Esercizio 1 L'automa a…