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 | |
|---|---|---|
| 1° | ABAABA | BB |
| 2° | BAAABABB | BBBB |
| 3° | BBB | BBB |
Diagramma di stato
- 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.
Quintuple
(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 |