Esercizio MdT (Macchina di Turing)
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 ?
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 ?
Risposte
Un piccolo commento. Questi argomenti, seppur possano rientrare nella logica sono più propriamente di informatica teorica e a matematica non si studiano. Sono quindi stato indeciso di spostarli in informatica, ma gli argomenti erano un po' a cavallo e avevi ricevuto risposta perciò ho evitato. Però su alcune tue domande potresti avere più risposte in informatica. Semmai sposto, vediamo come prosegue.
"vict85":
Un piccolo commento. Questi argomenti, seppur possano rientrare nella logica sono più propriamente di informatica teorica e a matematica non si studiano. Sono quindi stato indeciso di spostarli in informatica, ma gli argomenti erano un po' a cavallo e avevi ricevuto risposta perciò ho evitato. Però su alcune tue domande potresti avere più risposte in informatica. Semmai sposto, vediamo come prosegue.
An va benissimo ti ringrazio
Ciao 
Questa scrittura per la macchina di Turing non la conosco però ti posso dire che per il tuo esercizio una variabile non ti serve. Puoi infatti partire da uno stato in cui sai che la lunghezza della stringa è dispari (perché hai letto un simbolo) e passare ad un altro (in cui di conseguenza sai che la lunghezza è pari perché prima eri in uno stato in cui sapevi che era dispari) finché hai simboli della tua stringa da leggere. Una volta che non hai più simboli da leggere allora procedi a ritroso fino all'inizio della stringa (tenendo conto dello stato da cui provieni) ed arrivi fino al carattere prima dell'inizio della stessa. Ti sposti a destra ed ora, se provenivi dallo stato in cui avevi una lunghezza pari della stringa sei a posto altrimenti sovrascrivi il primo simbolo, ti sposti a destra e fine.
Questa scrittura per la macchina di Turing non la conosco però ti posso dire che per il tuo esercizio una variabile non ti serve. Puoi infatti partire da uno stato in cui sai che la lunghezza della stringa è dispari (perché hai letto un simbolo) e passare ad un altro (in cui di conseguenza sai che la lunghezza è pari perché prima eri in uno stato in cui sapevi che era dispari) finché hai simboli della tua stringa da leggere. Una volta che non hai più simboli da leggere allora procedi a ritroso fino all'inizio della stringa (tenendo conto dello stato da cui provieni) ed arrivi fino al carattere prima dell'inizio della stessa. Ti sposti a destra ed ora, se provenivi dallo stato in cui avevi una lunghezza pari della stringa sei a posto altrimenti sovrascrivi il primo simbolo, ti sposti a destra e fine.
"onlyReferee":
Ciao
Questa scrittura per la macchina di Turing non la conosco però ti posso dire che per il tuo esercizio una variabile non ti serve. Puoi infatti partire da uno stato in cui sai che la lunghezza della stringa è dispari (perché hai letto un simbolo) e passare ad un altro (in cui di conseguenza sai che la lunghezza è pari perché prima eri in uno stato in cui sapevi che era dispari) finché hai simboli della tua stringa da leggere. Una volta che non hai più simboli da leggere allora procedi a ritroso fino all'inizio della stringa (tenendo conto dello stato da cui provieni) ed arrivi fino al carattere prima dell'inizio della stessa. Ti sposti a destra ed ora, se provenivi dallo stato in cui avevi una lunghezza pari della stringa sei a posto altrimenti sovrascrivi il primo simbolo, ti sposti a destra e fine.
Come faccio a memorizzare uno stato di lunghezza pari/dispari?
Ho fatto così:
\( q_{0}xxq_{0}R \)
\( q_{1}xxq_{1}R \)
.....
\( q_{|alpha|+1}BBq_{|alpha|+1}L \) <---- qui sono arrivato alla fine quindi lo stato $|alpha| + 1$ quindi mi sposto a sinistra e vado allo stato $|alpha| - 1$ che è proprio la lunghezza della stringa. E ora?
Allora. Intanto quando sei nello stato iniziale non hai ancora letto nulla e pertanto non possiamo essere in uno stato in cui possiamo affermare che la lunghezza della porzione di stringa letta finora è pari/dispari. Pertanto ti servono sicuramente due stati $q_1$ e $q_2$ a questo scopo. Le tue prime transizioni vanno dunque modificate nel modo seguente (dove $q_1$ è lo stato per la lunghezza dispari e $q_2$ quello per la lunghezza pari):
$$
q_o xx q_1 R\\
q_1 xx q_2 R\\
q_2 xx q_1 R
$$
Ora devi appunto gestire il caso in cui sei arrivato alla fine sia a partire da $q_1$ che da $q_2$ (questo è il modo più semplice per "memorizzare" il fatto che la lunghezza della nostra stringa è pari/dispari). Pertanto ti servono due ulteriori stati in cui rimani finché non leggi $B$ (blank). Una volta che leggi $B$ dallo stato relativo alla lunghezza pari della stringa sei a posto e puoi transire nello stato finale, nell'altro caso invece ti servirà un ulteriore stato da cui effettuerai la sovrascrittura di $B$ (al posto del primo carattere della stringa)
Osservando bene come svolgi l'esercizio sono riuscito a capire come funziona questa scrittura qxypR/L.
$$
q_o xx q_1 R\\
q_1 xx q_2 R\\
q_2 xx q_1 R
$$
Ora devi appunto gestire il caso in cui sei arrivato alla fine sia a partire da $q_1$ che da $q_2$ (questo è il modo più semplice per "memorizzare" il fatto che la lunghezza della nostra stringa è pari/dispari). Pertanto ti servono due ulteriori stati in cui rimani finché non leggi $B$ (blank). Una volta che leggi $B$ dallo stato relativo alla lunghezza pari della stringa sei a posto e puoi transire nello stato finale, nell'altro caso invece ti servirà un ulteriore stato da cui effettuerai la sovrascrittura di $B$ (al posto del primo carattere della stringa)
Osservando bene come svolgi l'esercizio sono riuscito a capire come funziona questa scrittura qxypR/L
.
"onlyReferee":
Allora. Intanto quando sei nello stato iniziale non hai ancora letto nulla e pertanto non possiamo essere in uno stato in cui possiamo affermare che la lunghezza della porzione di stringa letta finora è pari/dispari. Pertanto ti servono sicuramente due stati $q_1$ e $q_2$ a questo scopo. Le tue prime transizioni vanno dunque modificate nel modo seguente (dove $q_1$ è lo stato per la lunghezza dispari e $q_2$ quello per la lunghezza pari):
$$
q_o xx q_1 R\\
q_1 xx q_2 R\\
q_2 xx q_1 R
$$
Ora devi appunto gestire il caso in cui sei arrivato alla fine sia a partire da $q_1$ che da $q_2$ (questo è il modo più semplice per "memorizzare" il fatto che la lunghezza della nostra stringa è pari/dispari). Pertanto ti servono due ulteriori stati in cui rimani finché non leggi $B$ (blank). Una volta che leggi $B$ dallo stato relativo alla lunghezza pari della stringa sei a posto e puoi transire nello stato finale, nell'altro caso invece ti servirà un ulteriore stato da cui effettuerai la sovrascrittura di $B$ (al posto del primo carattere della stringa)
Osservando bene come svolgi l'esercizio sono riuscito a capire come funziona questa scrittura qxypR/L
Non riesco a capire bene il tuo svolgimento delle prime transizioni:
$$
q_o xx q_1 R\\
q_1 xx q_2 R\\
q_2 xx q_1 R
$$
Correggimi se sbaglio, si leggono così queste transizioni?
"Sono in q0 leggo x scrivo x vado in q1 e mi sposto a destra"
"sono in q1 leggo x scrivo x vado in q2 e mi sposto a destra"
"sono in q2 leggo x scrivo x vado in q1 e mi sposto a destra"
Quando mi sposto a destra significa che vado alla destra dell'ultimo stato che sto scrivendo?
Quindi:
Nel caso di \( q_2 xx q_1 R \) , supponiamo che la piccola + sia il puntatore e che q0, q1 e q2 gli stati. Alla fine di questa transizione il puntatore sarà in q3?
-------------------------+
|-| --- |-| --- |-| --- |-|
q0 --- q1 --- q2 --- q4
Mi sta venendo il dubbio che forse non capisco come si leggono quelle transizioni...
Le transizioni le leggi nella maniera corretta, non hai però ancora capito il ragionamento. Noi non abbiamo uno stato per ogni carattere della stringa altrimenti vorrebbe dire che per ogni stringa di lunghezza diversa dalla precedente dovresti crearti una nuova macchina di Turing Noi abbiamo tanti stati quanti ce ne servono all'occorrenza per risolvere il nostro problema indipdentemente dal fatto di avere una stringa lunga uno, due, quattro o cinquanta caratteri. A ciascuno stato si attribuisce il significato di una particolare situazione in cui mi trovo durante il processo risolutivo del mio problema.
Pertanto, volendo rispondere alla tua domanda, nella transizione $q_2 x x q_1 R$ torno dallo stato $q_2$ a $q_1$ per il semplice fatto che se è vero che in $q_2$ ho una lunghezza pari della mia stringa, leggendo un altro carattere (il successivo) la stessa diventerà dispari e tale situazione mi è rappresentata dallo stato $q_1$. Se ci pensi bene in un automa deterministico/non deterministico così come lo conosciamo viene effettuata più di qualche volta una transizione da uno stato al precedente...
Noi abbiamo tanti stati quanti ce ne servono all'occorrenza per risolvere il nostro problema indipdentemente dal fatto di avere una stringa lunga uno, due, quattro o cinquanta caratteri. A ciascuno stato si attribuisce il significato di una particolare situazione in cui mi trovo durante il processo risolutivo del mio problema.Pertanto, volendo rispondere alla tua domanda, nella transizione $q_2 x x q_1 R$ torno dallo stato $q_2$ a $q_1$ per il semplice fatto che se è vero che in $q_2$ ho una lunghezza pari della mia stringa, leggendo un altro carattere (il successivo) la stessa diventerà dispari e tale situazione mi è rappresentata dallo stato $q_1$. Se ci pensi bene in un automa deterministico/non deterministico così come lo conosciamo viene effettuata più di qualche volta una transizione da uno stato al precedente...
"onlyReferee":
Le transizioni le leggi nella maniera corretta, non hai però ancora capito il ragionamento. Noi non abbiamo uno stato per ogni carattere della stringa altrimenti vorrebbe dire che per ogni stringa di lunghezza diversa dalla precedente dovresti crearti una nuova macchina di Turing
Pertanto, volendo rispondere alla tua domanda, nella transizione $q_2 x x q_1 R$ torno dallo stato $q_2$ a $q_1$ per il semplice fatto che se è vero che in $q_2$ ho una lunghezza pari della mia stringa, leggendo un altro carattere (il successivo) la stessa diventerà dispari e tale situazione mi è rappresentata dallo stato $q_1$. Se ci pensi bene in un automa deterministico/non deterministico così come lo conosciamo viene effettuata più di qualche volta una transizione da uno stato al precedente...
Ho capito il ragionamento adesso, ma non so se ho capito come si risolve
Allora ho provato in questo modo:
\( q_0xxq_1R \)
\( q_1xxq_2R \)
\( q_2xxq_1R \)
------
\( q_2BBq_3L \)
\( q_3xxq_0L \)
\( q_0xBq_0R \)
E corretto?
Le prime tre transazioni sono ok, la quarta anche, Nella quinta al posto di $q_0$ ci va $q_3$: siccome ora stiamo "tornando indietro" ed abbiamo già memorizzato l'informazione che volevamo sapere (la lunghezza della stringa che è pari) finché non arriviamo al $B$ presente prima del primo carattere della stringa non ha senso cambiare stato. Lo stesso ragionamento appena svolto devi poi replicarlo per lo stato $q_1$ (in questo caso ti servirà un altro stato in cui transire che possiamo chiamare $q_4$). L'ultima transizione non è corretta (non ci deve proprio essere perché oltre a quella iniziale che hai scritto non ve ne sono altre da/per $q_0$).
Intanto metti a posto queste transizioni, in seguito ti serviranno altri due stati e tre transizioni per completare l'esercizio.
Intanto metti a posto queste transizioni, in seguito ti serviranno altri due stati e tre transizioni per completare l'esercizio.
"onlyReferee":
Le prime tre transazioni sono ok, la quarta anche, Nella quinta al posto di $q_0$ ci va $q_3$: siccome ora stiamo "tornando indietro" ed abbiamo già memorizzato l'informazione che volevamo sapere (la lunghezza della stringa che è pari) finché non arriviamo al $B$ presente prima del primo carattere della stringa non ha senso cambiare stato. Lo stesso ragionamento appena svolto devi poi replicarlo per lo stato $q_1$ (in questo caso ti servirà un altro stato in cui transire che possiamo chiamare $q_4$). L'ultima transizione non è corretta (non ci deve proprio essere perché oltre a quella iniziale che hai scritto non ve ne sono altre da/per $q_0$).
Intanto metti a posto queste transizioni, in seguito ti serviranno altri due stati e tre transizioni per completare l'esercizio.
Può essere giusta così:
\( q_0xxq_1R \)
\( q_1xxq_2R \)
\( q_2xxq_1R \)
\( q_2xxq_3L \)
\( q_3xxq_3L \)
\( q_1xxq_4L \)
\( q_4xxq_4L \)
\( q_4BBq_5R \)
\( q_5xBq_5R \)
?
Ti riepilogo le correzioni nell'ordine:
Ok
Ok
Ok
La transizione corretta è: $q_2 B B q_3 L$ (il cambio lo stato lo fai quando leggi $B$ perché hai terminato la stringa)
Ok
La transizione corretta è: $q_1 B B q_4 L$ (vedi prima correzione, stesso motivo)
Ok
Ok
La transizione corretta è: $q_5 x B q_6 L$ (ti serve uno stato finale per accettare la stringa)
Manca infine la transizione da $q_3$ allo stato finale $q_6$ (bisogna riposizionarsi all'inizio della stringa di output anche nel caso di lunghezza pari, operazione necessaria in qualsiasi macchina di Turing): $q_3 B B q_6 L$ (come per $q_4$ il cambio lo stato lo fai quando leggi $B$ perché hai terminato la stringa).
Ok
Ok
Ok
La transizione corretta è: $q_2 B B q_3 L$ (il cambio lo stato lo fai quando leggi $B$ perché hai terminato la stringa)
Ok
La transizione corretta è: $q_1 B B q_4 L$ (vedi prima correzione, stesso motivo)
Ok
Ok
La transizione corretta è: $q_5 x B q_6 L$ (ti serve uno stato finale per accettare la stringa)
Manca infine la transizione da $q_3$ allo stato finale $q_6$ (bisogna riposizionarsi all'inizio della stringa di output anche nel caso di lunghezza pari, operazione necessaria in qualsiasi macchina di Turing): $q_3 B B q_6 L$ (come per $q_4$ il cambio lo stato lo fai quando leggi $B$ perché hai terminato la stringa).
"onlyReferee":
Ti riepilogo le correzioni nell'ordine:
Ok
Ok
Ok
La transizione corretta è: $q_2 B B q_3 L$ (il cambio lo stato lo fai quando leggi $B$ perché hai terminato la stringa)
Ok
La transizione corretta è: $q_1 B B q_4 L$ (vedi prima correzione, stesso motivo)
Ok
Ok
La transizione corretta è: $q_5 x B q_6 L$ (ti serve uno stato finale per accettare la stringa)
Manca infine la transizione da $q_3$ allo stato finale $q_6$ (bisogna riposizionarsi all'inizio della stringa di output anche nel caso di lunghezza pari, operazione necessaria in qualsiasi macchina di Turing): $q_3 B B q_6 L$ (come per $q_4$ il cambio lo stato lo fai quando leggi $B$ perché hai terminato la stringa).
Ricapitolando quindi:
\( q_0xxq_1R \)
\( q_1xxq_2R \)
\( q_2xxq_1R \)
\( q_2BBq_3L \)
\( q_3xxq_3L \)
\(q_3BBq_6L\)
\( q_1BBq_4L \)
\( q_4xxq_4L \)
\( q_4BBq_5R \)
\( q_5xBq_6R \)
Ok, ora ci siamo . Ti sono chiare le correzioni 
. Ti sono chiare le correzioni
"onlyReferee":
Ok, ora ci siamo
Più o meno sì
ora provo a farne un altro e magari posto qui le mie soluzioni così per capire se l'ho fatto giusto o meno Grazie mille in ogni caso
Ecco, allora ne ho un altro che dice così:
"Si definisca una macchia di Turing M su un alfabeto di simboli a,b,c che verifica se la stringa in ingresso comincia per abb, in caso positivo rimpiazza tale prefisso con cc, mentre lascia immutata la stringa di ingresso nel caso in cui quest'ultima non cominci per abb."
Io l'ho risolto così:
\( q_0aaq_1R \)
\( q_1bbq_2R \)
\( q_2bbq_3L \)
\( q_3BBq_4R \)
\( q_4aBq_1R \)
\(q_1bcq_2R\)
\( q_2bcq_3R \)
\( q_3BBq_5R \)
\( q_1BBq_6R \)
E' corretto?
"Si definisca una macchia di Turing M su un alfabeto di simboli a,b,c che verifica se la stringa in ingresso comincia per abb, in caso positivo rimpiazza tale prefisso con cc, mentre lascia immutata la stringa di ingresso nel caso in cui quest'ultima non cominci per abb."
Io l'ho risolto così:
\( q_0aaq_1R \)
\( q_1bbq_2R \)
\( q_2bbq_3L \)
\( q_3BBq_4R \)
\( q_4aBq_1R \)
\(q_1bcq_2R\)
\( q_2bcq_3R \)
\( q_3BBq_5R \)
\( q_1BBq_6R \)
E' corretto?
Sono corrette soltanto le prime tre transizioni. In realtà la terza, seppur corretta, ti fa eseguire un movimento in più della testina inutilmente quando potresti fare subito la sostituzione della $b$ con la $c$. Poi nelle tue transizioni supponi che la stringa sia comunque formata da almeno tre caratteri ma ciò non è detto che sia sempre vero chiaramente... Infine è sufficiente anche uno stato in meno rispetto a quelli che hai utilizzato.
Ti riporto di seguito la verisone corretta (quando scrivo R/L intendo che la testina rimane ferma nella propria posizione; nella stragrande maggioranza delle scritture per la macchina di Turing ciò è permesso, spero di non commettere un abuso di notazione con la scrittura corrente che adotti nell'esercizio):
$q_0 a a q_1 R$
$q_0 b b q_5 R \text{/} L$
$q_0 c c q_5 R \text{/} L$
$q_0 B B q_5 R \text{/} L$
$q_1 a a q_5 L$
$q_1 b b q_2 R$
$q_1 c c q_5 L$
$q_1 B B q_5 L$
$q_2 a a q_4 L$
$q_2 b c q_3 L$
$q_2 c c q_4 L$
$q_2 B B q_4 L$
$q_3 b c q_3 L$
$q_3 a B q_5 R$
$q_4 b b q_5 L$
Come si può intuire lo stato $q_5$ è quello finale.
Ti riporto di seguito la verisone corretta (quando scrivo R/L intendo che la testina rimane ferma nella propria posizione; nella stragrande maggioranza delle scritture per la macchina di Turing ciò è permesso, spero di non commettere un abuso di notazione con la scrittura corrente che adotti nell'esercizio):
$q_0 a a q_1 R$
$q_0 b b q_5 R \text{/} L$
$q_0 c c q_5 R \text{/} L$
$q_0 B B q_5 R \text{/} L$
$q_1 a a q_5 L$
$q_1 b b q_2 R$
$q_1 c c q_5 L$
$q_1 B B q_5 L$
$q_2 a a q_4 L$
$q_2 b c q_3 L$
$q_2 c c q_4 L$
$q_2 B B q_4 L$
$q_3 b c q_3 L$
$q_3 a B q_5 R$
$q_4 b b q_5 L$
Come si può intuire lo stato $q_5$ è quello finale.
Ho un altro esercizio che purtroppo non so proprio come fare... Ho una MdT che presa in input una stringa formata da a, b, c se questa inizia con una ripetizione di una lettera, quindi Aa, bb, cc, allora devo cancellare una delle due lettere, altrimenti restituisco la stringa così com é.
Come si può risolvere nella maniera più generale possibile?
Come si può risolvere nella maniera più generale possibile?
Allora, un possibile schema per procedere potrebbe essere il seguente. Se leggi subito $B$ vai direttamente nello stato di accettazine. Se leggi $a, b$ o $c$ allora cambi stato e ti sposti verso destra (ti servono tre stati in base alla lettera letta). Ora leggi il secondo carattere in ciascuno di questi nuovi stati. Se è diverso da quello letto in precedenza allora sposti la testina a sinistra e vai direttamente nello stato di accettazione. Se è invece uguale allora sposti la testina a sinistra e vai in un nuovo stato. Da lì rimpiazzi il simbolo letto (che può essere sia $a$ che $b$ che $c$) con il carattere $B$, sposti la testina a destra e vai nello stato di accettazione. Prova a tradurlo in istruzioni
"onlyReferee":
Allora, un possibile schema per procedere potrebbe essere il seguente. Se leggi subito $B$ vai direttamente nello stato di accettazine. Se leggi $a, b$ o $c$ allora cambi stato e ti sposti verso destra (ti servono tre stati in base alla lettera letta). Ora leggi il secondo carattere in ciascuno di questi nuovi stati. Se è diverso da quello letto in precedenza allora sposti la testina a sinistra e vai direttamente nello stato di accettazione. Se è invece uguale allora sposti la testina a sinistra e vai in un nuovo stato. Da lì rimpiazzi il simbolo letto (che può essere sia $a$ che $b$ che $c$) con il carattere $B$, sposti la testina a destra e vai nello stato di accettazione. Prova a tradurlo in istruzioni
Ok, allora può essere corretta una soluzione del genere:
\( q_0aaq_1R \)
\( q_1aaq_2L \)
\( q_2aBq_8R \)
\( q_0bbq_3R \)
\( q_3bbq_4L \)
\( q_4aBq_8R \)
\( q_0ccq_5R \)
\( q_5ccq_6L \)
\( q_6cBq_8R \)
\( q_7xxq_8R \)
\( q_8xxq_8R \)
\( q_1bbq_8R \)
\( q_1ccq_8R \)
\( q_3ccq_8R \)
\( q_3aaq_8R \)
\( q_5aaq_8R \)
\( q_5bbq_8R \)
?
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.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo