admin

Dato un numero intero positivo n, (n div 2) è il quoziente della divisione intera.Ad esempio, (6 div 2) è il numero 3, mentre (9 div 2) è il numero 4. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n A consecutive (con n > 1), termina la … Leggi tutto

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, con almeno una B, termina la sua esecuzione lasciando sul nastro la sequenza di sole B consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le A. Esempi Nastro iniziale Nastro finale … Leggi tutto

Indichiamo con s e t due generiche sequenze formate da A e B. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo sCtC, termina la sua esecuzione lasciando sul nastro la sequenza SI se S e T sono uguali, la sequenza NO altrimenti. Esempi Nastro iniziale Nastro finale 1° … Leggi tutto

Numeri Trini Un numero intero si dice trino se è divisibile per 3.Se n è trino, n+1 si dice strino e n+2 distrino. Si scriva un programma che, dato in input un numero decimale, lasci sul nastro una delle tre stringhe TRINO, STRINO o DISTRINO a seconda dei casi. Nastro iniziale Nastro finale 1° 3 TRINO 2° … Leggi tutto

Completezza Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {C, H, O}, lasci sul nastro la scritta SI se la stringa in ingresso conteneva ciascuno dei caratteri dell’alfabeto almeno una volta (la stringa in questo caso si dice completa rispetto all’alfabeto), NO in caso contrario. Esempi … Leggi tutto

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 1° AAAABB A 2° AAABBBBB B 3° AAABBB C Diagramma di stato Quintuple

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