automate bi-directionnel

Messages : 40

Enregistré le : 14 févr. 2018 19:13

Re: automate bi-directionnel

Message par Inversion » 24 nov. 2021 11:45

Aucun souci, content d'avoir pu aider. :)
2019-2021 : MPSI-MP* Hoche

Messages : 2

Enregistré le : 16 janv. 2022 10:41

Re: automate bi-directionnel

Message par emeric.tourniaire » 16 janv. 2022 11:03

Inversion a écrit :
15 nov. 2021 17:34
Si 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).
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.

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.

Messages : 40

Enregistré le : 14 févr. 2018 19:13

Re: automate bi-directionnel

Message par Inversion » 16 janv. 2022 19:07

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.
2019-2021 : MPSI-MP* Hoche

Répondre