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 INIZIALE | NASTRO FINALE |
---|---|
COO | NO |
HCCO | SI |
COO | NO |
HHHHH | NO |
OHHHHC | SI |
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
(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,>) | … |