06 07 2011

Pagina 1

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…