Edizione I – Problema 5

Indichiamo con AⁿB^m una sequenza del tipo A…AB…B.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AⁿB^m, con n>0 e m>0, termina la sua esecuzione lasciando sul nastro

• una sola A se n>m
• una sola B se m>n
• una sola C se n=m.

Esempi

NASTRO INIZIALE	NASTRO FINALE
AAAABB	A
AAABBBBB	B
AAABBB	C

Algoritmo

• Cancella una A a sinistra, va a destra e cancella una B, ritorna a sinistra
• Ripete finché è possibile…
• Se finiscono le A cancella le B rimaste e scrive B
• Se finiscono le B cancella le A rimaste e scrive A
• Se finiscono sia le A che le B allora scrive C

Codice	Commenti
(0,A,A,-,>)	Ha trovato una A, va a destra
(0,B,BB,-,>)	Ha trovato una B, cancella tutto
(0,-,H,C,>)	Scrive C
(A,AB,A,AB,>)	Va a destra
(A,-,R,-,<)	In fondo…
(R,A,A,-,<)	Cancella tutte le A
(R,-,H,A,>)	Scrive A
(B,AB,B,AB,<)	Va a sinistra
(B,-,0,-,>)	In fondo…
(BB,B,BB,-,>)	Cancella tutte le B
(B,-,H,B,>)	Scrive B