Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, con almeno una B, termina la sua esecuzione lasciando sul nastro la sequenza di sole B consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le A.
Esempi
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| ABAABA | BB |
| BAAABABB | BBBB |
| BBB | BBB |
Algoritmo
- Se incontra una A la cancella
- Se incontra una B la cancella ma la riscrive a destra come X e ricomincia
- Quando le A e B finiscono traduce le X in B
| Codice | Commenti |
|---|---|
(0,A,0,-,>) | Elimina le A |
(0,B,B,-,>) | Elimina una B e va nello stato B |
(0,X,0,B,>) | Traduce le X in B |
(B,ABX,B,ABX,>) | Salta ABX per andare a destra |
(B,-,R,X,<) | Scrive X e ritorna |
(R,ABX,R,ABX,<) | Salta ABX per andare a sinistra |
(R,-,0,-,>) | Ricomincia |