QUESITI di GARA

Problema 1 Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro A…A (n consecutive). NASTRO INIZIALE NASTRO FINALE 1 A 5 AAAAA 9 AAAAAAAAA Problema 2 Programmare una macchina di Turing che, dato un nastro iniziale contenente … Leggi tutto

Problema 1 Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti. NASTRO INIZIALE NASTRO FINALE 148 SI 2763 NO Problema 2 Programmare … 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 la sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più B consecutive con una sola B. Esempi Nastro iniziale Nastro … Leggi tutto

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 3 TRINO 5 DISTRINO … 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 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