Edizione V – 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
1°	AABABBBAABAAABAABAA	ACDCDBBACDAACDACDAA
2°	BBBBAAA	BBBBAAA
3°	AABB	ACDB

Diagramma di stato

• 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…

Quintuple

(0,B,0,B,>)	Salta le B
(0,A,1,A,>)	Ha trovato una A
(1,A,1,A,>)	Salta le A
(1,B,2,D,<)	Ha trovato la B, scrive D
(2,A,3,C,>)	Scrive C
(3,D,0,D,>)	Salta la D e ricomincia