Edizione XII – Problema 3

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

Diagramma di stato

Osserva

• Il nome dello stato, C, H, O, CH, CO, HO, CHO, 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

Quintuple

(0, C, C, -, >)
(0, H, H, -, >) 
(0, O, O, -, >)
(C, C, C, -, >) 
(C, H, CH, -, >) 
(C, O, CO, -, >) 
(H, C, CH, -, >) 
(H, H, H, -, >)
(H, O, HO, -, >)
(O, C, CO, -, >)
(O, H, HO, -, >)
(O, O, O, -, >) 
(CH, [CH], CH, -, >)
(CH, O, CHO, -, >) 
(CO, [CO], CO,-, >)
(CO, H, CHO, -, >)
(HO, [HO], HO, -, >)
(HO, C, CHO, -, >)
(C, -, NO, N, >)
(CH, -, NO, N, >)
(CO, -, NO, N, >)
(H, -, NO, N, >)
(HO, -, NO, N, >)
(O, -, NO, N, >)
(NO, -, F, O, >)
(CHO, [CHO], CHO, -, >)
(CHO, -, SI, S, >) 
(SI, -, F, I, >)