automate bi-directionnel
Re: automate bi-directionnel
Je pense qu'il y a une confusion. L'objectif d'un automate (boustrophédon ou non) n'est pas de construire un mot mais de déterminer si un mot est reconnu ou non. Il n'est donc pas question d'utiliser les transitions pour ajouter ou supprimer des lettres, mais de savoir ici simplement dans quel ordre les lettres sont lues.Inversion a écrit : ↑15 nov. 2021 17:34Si la petite flèche va vers la droite, cela signifie que tu ajoutes l'élément de l'alphabet à la fin du mot que tu es en train de lire, et si la petite flèche va vers la gauche, tu l'ajoutes au contraire au début.
Par exemple si tu as :
q0 ---------> q1 --------------> q2 ------------> q3
|| a,<--- |||||| b,-----> |||||| b, <------
avec q0 l'état initial et q3 l'unique état final, alors le seul mot reconnu par ton automate sera bab (les barres verticales sont juste un outil artisanal pour bien aligner les éléments de l'alphabet et les petites flèches sous les flèches de transition).
Avec l'exemple donné plus haut (état $ q_0 $, une seule transition qui va vers la droite étiquetée par ←), et un mot $ u $ quelconque, l'automate sera initialement dans l'état $ q_0 $, et aura le mot u entier à lire. Si le mot $ u $ ne commence pas par un a, alors l'automate ne peut passer dans aucun état, la lecture s'arrête et le mot n'est pas accepté. Si le mot $ u $ commence par un a, alors l'automate passe dans l'état 1, mais avec une transition ←, et on se retrouve dans la situation décrite dans le sujet : « Si l’automate se trouve sur la lettre la plus à gauche du mot et qu’il effectue une transition qui l’amène encore plus à gauche, le calcul est interrompu et le mot n’est pas reconnu. » (page 3). Bref : cet automate reconnait le langage vide.
Re: automate bi-directionnel
Bonjour,
Merci pour votre réponse, d'avoir pris le temps d'intervenir et de corriger ma (grosse) faute.
Mes excuses au posteur initial pour mon erreur. J'espère qu'il pourra voir votre correction à l'avenir.
Bonne soirée.
Merci pour votre réponse, d'avoir pris le temps d'intervenir et de corriger ma (grosse) faute.
Mes excuses au posteur initial pour mon erreur. J'espère qu'il pourra voir votre correction à l'avenir.
Bonne soirée.