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 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…
First page of the document.
