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…
Tabella delle transizioni di stato
A
B
C
D
0
1, A, >
0, B, >
1
1, A, >
2, D, <
2
3, C, >
3
0, D, >
Quintuple
(0, B, 0, B, >)
(0, A, 1, A, >)
(1, A, 1, A, >)
(1, B, 2, D, <)
(2, A, 3, C, >)
(3, D, 0, D, >)
