Esercizio MdT (Macchina di Turing)

[JoKeRxbLaCk93]

Ciao a tutti, ho questo esercizio:
Si definisca una macchina di Turing M su un alfabeto di simboli a, b, c (oltre il blank) che presa una stringa in ingresso, produce in uscita la stessa stringa immutata, nel caso che questa abbia lunghezza pari, mentre cancella il suo primo simbolo, se la sua lunghezza è dispari. (Suggerimento: si usi la notazione qxypR/L dove x e y sono simboli generici sull'alfabeto della macchina, diversi dal Blank).

Ora il metodo dovrebbe essere il seguente: scorro il nastro a partire dallo stato iniziale q0 verso destra e ad ogni passaggio dovrò "memorizzare" in una specie di variabile un numero che incremento ogni qual volta cambio stato (ma come posso fare?), poi appena arrivo al carattere Blank mi fermo. Faccio il controllo se la variabile dove ho memorizzato il numero è pari o dispari, nel caso in cui è dispari mi sposto di stato in stato verso sinistra fino a che non raggiungo il carattere Blank, una volta raggiunto mi sposto a destra di uno stato e metto il carattere Blank anzichè il carattere presente.

Come posso implementare una cosa del genere? con la scrittura qxypR/L ?

[JoKeRxbLaCk93]

"onlyReferee":Allora, intanto ci sono troppi stati, più del necessario. Te ne bastano semplicemente sei (da $q_0$ a $q_5$). Lo scopo di $q_7$ (stato che non viene mai raggiunto) non l'ho proprio capito, così come la transizione da $q_8$ a sé stesso.
Poi...Come dicevamo le altre volte anche se non si deve modificare la stringa bisogna comunque tornare alla sua posizione iniziale prima di giungere allo stato finale. In questo modo la testina risulta allineata all'inizio della nostra stringa in output.
Infine non hai considerato il caso di poter leggere il simbolo $B$ (sia in presenza di una stringa vuota che di una stringa di due o meno caratteri).
In sostanza ci sono molte transizioni da sistemare. Il mio consiglio, in questo come in altri esercizi, è quello di prenderti un po' di tempo e farti uno schemino passo passo di ciò che accade alla stringa man mano che annoti le transizioni.

Ho provato a risolvere l'esercizio nella maniera più generale possibile :

q0xxq1R
q1xxq2L
q2xBq3R
q3BBq4L
q1yyq3R

Cosi facendo se nei primi due stati ho la stessa lettera sostituisco un Blank altrimenti vado avanti a leggere finché non arrivo ai Blank finali, potrebbe essere corretto?

[onlyReferee]

No perché per "tenere memoria" della lettera che hai letto devi andare da $q_0$ in stati diversi. Nelle transizioni presenti nel tuo thread precedente avevi iniziato benino solo che poi ti sei perso per strada. Prova a ragionarci bene e con calma seguendo quanto ho scritto nei post precedenti...