Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra.
Se la sequenza iniziale è composta da sole cifre 0, la macchina deve lasciare sul nastro un solo 0.
Esempi
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 000431 | 431 |
| 0000 | 0 |
| 004031 | 4031 |
| 431 | 431 |
Diagramma di stato
- Elimina gli 0 a partire da sinistra
- Se incontra lo spazio scrive 0 e finisce
- Se incontra una cifra diversa da 0 si ferma…
(0,0,0,-,>) | Elimina gli 0 |
(0,-,H,0,-) | Si ferma e scrive 0 |