ESERCIZI di GARA

Programmare una macchina di Turing che simuli il comportamento di una versione semplificata di macchina di Turing rappresentata come segue. La macchina si programma con quintuple, gli stati sono rappresentati da sequenze di ‘S’, mentre i simboli accettati sono 1, 0 e N (che rappresenta il blank o spazio). Una quintupla descritta da <stato><car><stato><car><dir> viene … Leggi tutto

Problema 1 Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro il bit di parità. Tale bit è 1 se e solo se vi sono un numero dispari di 1 nella sequenza iniziale; altrimenti vale 0. NASTRO INIZIALE NASTRO … Leggi tutto

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