Sequenza palindroma > A..Z

Tratto dal sito ufficiale

Scrivere un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto a-z, lasci il nastro vuoto alla fine della computazione se e solo se la stringa originale era palindroma.

Si dicono palindrome le stringhe che si leggono identicamente da sinistra a destra o da destra verso sinistra.

Esempi

NASTRO INIZIALE NASTRO FINALE
ailatiditalia
ailatidtalia d
satorras torr

Algoritmo

  1. Posizionati sul primo carattere a sinistra della stringa, lo cancelliamo, memorizziamo nel nome dello stato il carattere letto, passando nello stato lettoa (se abbiamo letto una a) fino a lettoz (se abbiamo letto una z).
  2. Quindi scorriamo tutta la stringa, mantenendo memoria nello stato di quale carattere avevamo letto, e riscrivendo sempre il carattere letto.
  3. Arrivati in fondo alla stringa, ci spostiamo di una cella a destra (sempre mantenendo il carattere letto originalmente nello stato), e verifichiamo di trovare all’estremit√† sinistra della stringa lo stesso carattere che avevamo letto a destra.
  4. In caso positivo, si cancella il carattere e si ritorna in cima alla stringa, ripetendo poi l’algoritmo (fino a consumare tutta la stringa).
  5. In caso negativo si interrompe il calcolo, lasciando sul nastro la parte di stringa non palindroma.

Codice 1

(0,[a..z],letto[a..z],-,>)
(letto[a..z],{a..z},letto[a..z],{a..z},>)
(letto[a..z],-,destra[a..z],-,<)
(destra[a..z],[a..z],ritorno,-,<)
(ritorno,[a..z],ritorno,[a..z],<) (ritorno,-,0,-,>)
Notice: This work is licensed under a BY-NC-SA. Permalink: Sequenza palindroma > A..Z

Comments are closed.