Version imprimable
Bonsoir,
Je voudrai faire décaler un mot de l'alphabet {0, 1} d'une position à droite dans le ruban de Turing.
j'ai raisonné comme suit:
On se déplace à droite
q0, $, $, droite, q1
On se place à l'autre bout du mot
q1, 1, 1, droite, q1
q1, 0, 0, droite, q1
Arrivé à la fin
q1, #, #, droite, q2
maintenant je n'arrive pas à trouver comment réécrire chaque symbole en remplaçant les blancs.
Je sais qu'il y a surement une meilleure idée pour faire ce décalage :?
Help please
Ta dernière transition devrait plutôt être :
q1, #, #, gauche, q2
Puis :
q2, 0, #, droite, q3
q2, 1, #, droite, q4
q3, #, 0, gauche, q1
q4, #, 1, gauche, q1
Et la machine s'arrêtera lorsque q2 rencontrera un blanc.
--
Jedaï
Merci j'ai déroulé et j'ai très bien compris les transitions.Citation:
Envoyé par Jedai
mais je ne vois pas comment q2 pourrait rencontrer un blanc! ce n'est pas un $ qui va indiquer l'arrêt?
Bonsoir,
si tu veux décaler ton mot vers la droite, il te faut démarrer de la gauche :)
Tu démarres d'un état initial qui mémorise le premier symbole et le remplace par ton symbole vide.
Ensuite, tu sauvegardes ton état en remplaçant par l'état précédent ainsi de suite jusqu'à arriverà la droite du mot.
Merci je crois que c'est ce qu'on a fait pour décaler le mot à droite.Citation:
Envoyé par ToTo13
maintenant pour le décaler à gauche c'est presque la même procédure sauf qu'au lieu de démarrer de la gauche on démarre de la droite. non?
Je n'avais pas fait attention mais si effectivement ton ruban est rempli de $ avant les données (ou tu as un ruban semi-infini), effectivement q2 ne rencontrera pas de blanc mais bien le premier $.Citation:
Envoyé par acacia
En tout cas il s'arrêtera, après je n'ai pas toutes les spécifications de tes machines de Turing donc je ne sais pas très bien comment signaler un succès, mais par exemple si tu utilises un état pour signaler le succès, tu peux rajouter cette transition :
q2, $, $, _, qSuccès
Néanmoins la proposition de Toto13 est plus efficace, un seul parcours suffit pour effectuer le décalage d'un rang vers la droite :
q0, $, $, droite, q1
q1, 0, #, droite, q2 -- # ou $ selon ta convention ??
q1, 1, #, droite, q3 -- idem
q2, 0, 0, droite, q2
q2, 1, 0, droite, q3
q2, #, 0, _, qSuccès
q3, 0, 1, droite, q2
q3, 1, 1, droite, q3
q3, #, 1, _, qSuccès
--
Jedaï
Je pense que c'est la meilleure façon de faire : un seul parcours avec mémorisation.Citation:
Envoyé par Jedai
Je vous remercie beaucoup pour vos explications.
Le $ est un caractère qui marque le début du ruban et on ne peut l'effacer ou le remplacer, par contre le # signifie un blanc.Citation:
q0, $, $, droite, q1
q1, 0, #, droite, q2 -- # ou $ selon ta convention ??
q1, 1, #, droite, q3 -- idem
q2, 0, 0, droite, q2
q2, 1, 0, droite, q3
q2, #, 0, _, qSuccès
q3, 0, 1, droite, q2
q3, 1, 1, droite, q3
q3, #, 1, _, qSuccès