Edizione V – Problema 1

di

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 INIZIALENASTRO FINALE
AABABBBAABAAABAABAAACDCDBBACDAACDACDAA
BBBBAAABBBBAAA
AABBACDB

Algoritmo

  • Salta eventuali B iniziali.
  • Una A potrebbe essere l’inizio della sequenza AB. Salta eventuali altre A.
  • Se arriva B scrive D, torna indietro e scrive C, ricomincia…
CodiceCommenti
(0,B,0,B,>)Salta le B
(0,A,A,A,>)Ha trovato una A
(A,A,A,A,>)Salta le A
(A,B,X,D,<)Ha trovato la B, scrive D
(X,A,Y,C,>)Scrive C
(Y,D,0,D,>)Salta la D e ricomincia

Lascia un commento