ESERCIZI di GARA

Indichiamo con AnBm una sequenza del tipo A…AB…B. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AnBm, con n>0 e m>0, termina la sua esecuzione lasciando sul nastro Esempi NASTRO INIZIALE NASTRO FINALE AAAABB A AAABBBBB B AAABBB C Diagramma di stato Quintuple (0,A,A,-,>) Ha trovato una A, … Leggi tutto

Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è … Leggi tutto

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra. Se la sequenza iniziale è composta da sole cifre 0, la macchina … Leggi tutto

Problema 1 – Lo scorciatore In Informatica, una struttura dati è un modo di organizzare le informazioni nella memoria di un calcolatore in modo da facilitare l’esecuzione di un insieme predefinito di operazioni. La struttura dati più semplice è la sequenza, che può essere facilmente rappresentata da una sequenza di simboli sul nastro. Sulle sequenze … Leggi tutto

Problema 1 Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100. NASTRO INIZIALE NASTRO FINALE 431 43100 6 600 Problema 2 Programmare una Macchina di Turing che, dato un nastro … Leggi tutto

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti. Esempi Nastro iniziale Nastro finale 1 BABBAB T 2 B T 3 AAA F Diagramma di … Leggi tutto

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100. Esempi Nastro iniziale Nastro finale 1° 431 43100 2° 6 600 Diagramma di stato Si posiziona a destra.Scrive due volte 0. … Leggi tutto