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 Modulo di Informatica Teorica Appello del 6 luglio 2011 Tempo a disposizione: 1h30’ Esercizio 1 (11 punti) Si consideri il linguaggio L⊆{a,b,c}* composto dalle stringhe di lunghezza ≥2 che finiscono con 'bc', e una funzione di traduzione τ che, per ogni stringa x∈L, cancella i simboli 'a', raddoppia le 'b', e mantiene inalterate le 'c'. Per esempio τ(abc)=bbc, τ(cbabc)= cbbbbc, τ(c)=⊥, τ(cbab)= ⊥. • Si scriva il trasduttore finito che calcoli la traduzione descritta. • Si scriva l'automa a stati finiti che accetti il linguaggio τ(L); se possibile si mostri come l'automa che accetta τ(L) si possa derivare dal trasduttore definito precedentemente. • Basandosi sulla domanda precedente, si delinei una procedura sistematica per ottenere da un trasduttore a stati finiti, l'automa che accetti il linguaggio di uscita del trasduttore stesso. Esercizio 2 (10 punti) Si consideri un sistema composto da una lampada dotata di N>1 bottoni per accenderla e spegnerla. La lampada viene accesa premendo simultaneamente almeno due bottoni, mentre viene spenta premendo esattamente un bottone. Si descriva il sistema attraverso una rete di Petri oppure formule logiche, usando i seguenti predicati: L(t): la lampada è accesa al tempo t; P(b, t): il bottone b viene premuto al tempo t. Esercizio 3 (11 punti) Si consideri l'insieme di macchine di Turing (MT) a nastro singolo con n stati definite su un alfabeto prefissato. Come noto, c'è un numero finito di tali MT a n stati. Iniziando l'esecuzione con il nastro con tutti blank, alcune di queste MT terminano, mentre altre non terminano. 1. Dire se è decidibile il problema di stabilire se, data una generica MT dell’insieme considerato, questa termina partendo con il nastro con tutti blank. Si definisce S(n) il…
First page of the document.
