QUESITI di GARA

Problema 1 – Stringhe Trine Una stringa si dice trina se è della forma aaa, ovvero se è composta da tre parti uguali. Si scriva un programma che, ricevuta in ingresso una stringa sull’alfabeto {a, b, c}, lasci sul nastro al termine della computazione la stringa trina ottenuta triplicando la stringa di ingresso. NASTRO INIZIALE NASTRO … Leggi tutto

Problema 1 – Quadristringhe Una quadristringa è una stringa su un alfabeto dato che ha la forma XXXX, ovvero, che è composta di quattro parti uguali ripetute. Per esempio, abcabcabcabc è una quadristringa. Si scriva un programma che, data in ingresso una stringa sull’alfabeto a, b, c, lasci sul nastro SI se la stringa di ingresso … Leggi tutto

Edizione patrocinata dal Rotary Club di Pisa e aperta alle scuole della provincia di Pisa. Problema 1 – Ababa NO Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa composta di A e B, lasci sul nastro la scritta SI se la sequenza conteneva un numero uguale di A e … Leggi tutto

Problema 1 – Addizione unaria Nei sistemi di numerazione posizionale, il valore denotato da un numero è ottenuto moltiplicando ogni cifra per la corrispondente potenza di una base.Nel caso della notazione decimale, la base è 10; la cifra più a destra è moltiplicata per 100=1, quella successiva per 101=10, la terza da destra per 102=100, e … Leggi tutto

Problema 1 – Musica, musica! Tradizionalmente, le sette note della scala musicale vengono denominate in Italia do, re, mi, fa, sol, la, si.Le stesse note nel sistema anglosassone vengono indicate con le prime lettere dell’alfabeto: A, B, … G, con do re mi fa sol la si C D E F G A B Si scriva … Leggi tutto

Problema 1 Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N.Quando raggiunge il valore massimo 99…9, ritorna a 00…0. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul … Leggi tutto

Problema 1 – Sostituzione di caratteri Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A e B, sostituisca ogni occorrenza di due simboli consecutivi AB con due simboli CD. NASTRO INIZIALE NASTRO FINALE AABABBBAABAAABAABAA ACDCDBBACDAACDACDAA BBBBAAA BBBBAAA AABB ACDB Problema 2 – Parentesi bilanciate Una sequenza di parentesi quadre … Leggi tutto

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