Vai al contenuto

Edizione I – Problema 2

  • di

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 INIZIALENASTRO FINALE
BABBABT
BT
AAAF

Algoritmo

0102

  • 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
Codice #1Commenti
(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
Codice #2Commenti
(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

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *