Vai al contenuto

Edizione XII – Problema 3

  • di

Completezza

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {C, H, O}, lasci sul nastro la scritta SI se la stringa in ingresso conteneva ciascuno dei caratteri dell’alfabeto almeno una volta (la stringa in questo caso si dice completa rispetto all’alfabeto), NO in caso contrario.

Esempi

NASTRO INIZIALENASTRO FINALE
COONO
HCCOSI
COONO
HHHHHNO
OHHHHCSI

Algoritmo

1203_

  • Il nome dello stato, C, H, O, CH, CO, HOCHO, indica le lettere diverse incontrate fino a quel momento.
  • Se l’input finisce e si trova nello stato CHO scrive SI
  • Se si trova in un qualsiasi altro stato scrive NO
CodiceCommenti
(0,C,C,-,>)Nessun carattere letto
(0,H,H,-,>)
(0,O,O,-,>)
(C,C,C,-,>) Ha letto almeno una C
(C,H,CH,-,>)
(C,O,CO,-,>)
(H,C,CH,-,>) Ha letto almeno una H
(H,H,H,-,>)
(H,O,HO,-,>)
(O,C,CO,-,>)Ha letto almeno una O
(O,H,HO,-,>)
(O,O,O,-,>)
(CH,[CH],CH,-,>)Ha letto almeno una C e almeno una H
(CH,O,CHO,-,>)
(CO,[CO],CO,-,>)Ha letto almeno una C e almeno una O
(CO,H,CHO,-,>)
(HO,[HO],HO,-,>)Ha letto almeno una H e almeno una O
(HO,C,CHO,-,>)
(C,-,NO,N,>)Scrive NO
(CH,-,NO,N,>)
(CO,-,NO,N,>)
(H,-,NO,N,>)
(HO,-,NO,N,>)
(O,-,NO,N,>)
(NO,-,F,O,>)
(CHO,[CHO],CHO,-,>)Salta C, H, O
(CHO,-,SI,S,>) Scrive SI
(SI,-,F,I,>)

Lascia un commento

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