Edizione I – Problema 2

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti.

Esempi

	Nastro iniziale	Nastro finale
1	BABBAB	T
2	B	T
3	AAA	F

Diagramma di stato

• Lo stato 0 indica che non c’è alcuna B e se l’input finisce scrive F
• Lo stato 1 indica che c’è almeno una B e se l’input finisce scrive T

Quintuple #1

(0,A,0,-,>)	Finché A rimani in 0
(0,B,1,-,>)	Se B vai in 1
(0,-,H,F,>)	Se l’input è finito scrivi F
(1,A,1,-,>)	Finché A oppure B rimani in 1
(1,B,1,-,>)	…
(1,-,H,T,>)	Se l’input è finito scrivi T

Quintuple #2

(0,A,0,-,>)	Finché A rimani in 0
(0,B,1,-,>)	Se B vai in 1
(0,-,H,F,>)	Se l’input è finito scrivi F
(1,[AB],1,-,>)	Finché A oppure B rimani in 1
(1,-,H,T,>)	Se l’input è finito scrivi T