automate bi-directionnel

Messages : 2

Inscription : 14 nov. 2021 18:01

Profil de l'utilisateur : Élève de lycée

automate bi-directionnel

Message par clemparc » 14 nov. 2021 18:06

Bonjour,

Je suis en train de faire un sujet qui porte sur les automates bi-directionnels.
On le définit ainsi:
• un ensemble fini non vide Q d'états
• un état initial s
• un ensemble d'états finaux T
• une fonction de transition delta : Q x A -> Q x {L, R}.

Le hic c'est que j'ai du mal à comprendre comment on les représente. J'ai essayé avec des exemples basiques du genre un alphabet à deux lettres, etc. mais je ne comprends pas comment ça marche. Je sais qu'on peut lire les mots dans les deux sens mais du coup je ne comprends pas comment on utilise L et R dans le dessin des automates, etc.

Quelqu'un pourrait-il m'expliquer comment ça marche précisément?
Je vous en remercie !
(P.S. : je ne fais pas option info en prépa mais je le fais de mon côté, mais je pense être au point sur les automates)

Messages : 2471

Inscription : 27 juil. 2016 19:38

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel

Message par U46406 » 14 nov. 2021 18:21

Quel intérêt pour toi qui es en voie PC de t’intéresser au programme de l’option informatique de la voie MP, compte tenu des coefficients respectés des épreuves aux divers concours ?

Erratum : respectés / respectifs.


Edit : je ne vais pas intervenir plus - à ce sujet de la question d’un Hors programme - dans le fil à ta suite, pour que d’autres puissent répondre.

Mais à choisir un hobby de taupe, mieux vaut lire des articles en anglais sur des sujets technologies et sciences (pour mieux préparer les concours - une fois en école, tu seras plus libre de tes passes-temps).
Dernière modification par U46406 le 14 nov. 2021 21:48, modifié 2 fois.
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait) :mrgreen:

Messages : 2

Inscription : 14 nov. 2021 18:01

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel

Message par clemparc » 14 nov. 2021 20:39

c'est juste pour moi, c'est des choses qui m'intéressent, mais je n'y passe bien sûr pas beaucoup de temps pour les raisons que tu viens d'évoquer

ceci dit, quelqu'un saurait m'expliquer du coup? j'ai du mal à comprendre comment on représente ce genre d'automates et comment on les "lit" selon qu'on mette L ou R sur les flèches :x

Messages : 2471

Inscription : 27 juil. 2016 19:38

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel

Message par U46406 » 14 nov. 2021 21:46

Je n’y connais rien mais L : left et R : right end-marker ?

Marqueurs gauche et droit.


https://fr.wikipedia.org/wiki/Automate_ ... n_formelle

https://en.wikipedia.org/wiki/Two-way_finite_automaton
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait) :mrgreen:

Inversion

Re: automate bi-directionnel

Message par Inversion » 15 nov. 2021 11:34

Bonjour,

Si tu communiques le sujet, je veux bien essayer de t'aider. Sinon, je ne pense pas que je pourrai vraiment.

Messages : 2

Inscription : 15 nov. 2021 16:06

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel

Message par clemparc2 » 15 nov. 2021 16:12

Merci beaucoup pour vos réponses (j'ai dû recréer mon compte car mon mot de passe ne marchait plus...).
Inversion a écrit :
15 nov. 2021 11:34
Bonjour,

Si tu communiques le sujet, je veux bien essayer de t'aider. Sinon, je ne pense pas que je pourrai vraiment.
@Inversion j'ai pris le sujet de là (c'est l'exercice 6): http://www.lirmm.fr/~poupet/enseignemen ... iel-05.pdf
Cependant je voulais avant faire un exemple en dessinant un automate sur un alphabet à deux lettres par exemple, qui puisse reconnaître (par exemple) l'ensemble des mots ayant un nombre de lettres multiple de 4 et se terminant par b. Mais le truc avec les flèches me perturbe, est-ce que quand on dessine l'automate on ne met pas les flèches habituelles qu'on met dans les automates "normaux"? Je ne comprends pas trop. Merci !

Messages : 2471

Inscription : 27 juil. 2016 19:38

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel (cours de L3 ENS Lyon !!)

Message par U46406 » 15 nov. 2021 16:17

J'avais voulu ne plus m'exprimer à ce sujet, mais je constate que l'intitulé encapsulateur de ce sujet est... cours de Marianne Delorme en L3 à l'ENS Lyon ?!!
SPOILER:
L'OP est audacieux.
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait) :mrgreen:

Messages : 17

Inscription : 10 févr. 2021 10:49

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel

Message par Administrateur UPS » 15 nov. 2021 16:34

@U46406 : merci de limiter vos posts à ceux qui apportent de l'information ; donc éviter les posts du type "je n'y connais rien mais" ou encore "je ne voulais plus poster, mais [...]".
Administrateur du forum.

Inversion

Re: automate bi-directionnel

Message par Inversion » 15 nov. 2021 17:34

clemparc2 a écrit :
15 nov. 2021 16:12
Merci beaucoup pour vos réponses (j'ai dû recréer mon compte car mon mot de passe ne marchait plus...).
Inversion a écrit :
15 nov. 2021 11:34
Bonjour,

Si tu communiques le sujet, je veux bien essayer de t'aider. Sinon, je ne pense pas que je pourrai vraiment.
@Inversion j'ai pris le sujet de là (c'est l'exercice 6): http://www.lirmm.fr/~poupet/enseignemen ... iel-05.pdf
Cependant je voulais avant faire un exemple en dessinant un automate sur un alphabet à deux lettres par exemple, qui puisse reconnaître (par exemple) l'ensemble des mots ayant un nombre de lettres multiple de 4 et se terminant par b. Mais le truc avec les flèches me perturbe, est-ce que quand on dessine l'automate on ne met pas les flèches habituelles qu'on met dans les automates "normaux"? Je ne comprends pas trop. Merci !
Merci de m'avoir communiqué le sujet.
Si j'ai bien compris, quand tu dessines un automate boustrophédon, tu mets toujours les flèches que tu mets pour un automate "normal". Simplement, à chaque transition (donc à chaque "flèche normale" qui est surmontée d'un élément de l'alphabet), tu indiques une petite flèche qui va soit vers la gauche soit vers la droite. 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).

(d'abord tu ajoutes a par la transition (a, <---) puis par la transition (b, ---->) tu ajoutes b à la fin de ton mot ce qui fait ab puis par la transition (b, <-----) tu ajoutes b au début de ton mot ce qui fait bab).

C'est comme ça que je comprends la phrase "La capacité supplémentaire d’un automate boustrophédon par rapport à un automate
fini classique, est de pouvoir se déplacer sur le mot vers la droite et la gauche (là où un
automate fini ne peut qu’avancer vers la droite)."

Désolé pour le schéma un peu moyen.

Messages : 2

Inscription : 15 nov. 2021 16:06

Profil de l'utilisateur : Élève de lycée

Re: automate bi-directionnel

Message par clemparc2 » 22 nov. 2021 20:45

Inversion a écrit :
15 nov. 2021 17:34
clemparc2 a écrit :
15 nov. 2021 16:12
Merci beaucoup pour vos réponses (j'ai dû recréer mon compte car mon mot de passe ne marchait plus...).
Inversion a écrit :
15 nov. 2021 11:34
Bonjour,

Si tu communiques le sujet, je veux bien essayer de t'aider. Sinon, je ne pense pas que je pourrai vraiment.
@Inversion j'ai pris le sujet de là (c'est l'exercice 6): http://www.lirmm.fr/~poupet/enseignemen ... iel-05.pdf
Cependant je voulais avant faire un exemple en dessinant un automate sur un alphabet à deux lettres par exemple, qui puisse reconnaître (par exemple) l'ensemble des mots ayant un nombre de lettres multiple de 4 et se terminant par b. Mais le truc avec les flèches me perturbe, est-ce que quand on dessine l'automate on ne met pas les flèches habituelles qu'on met dans les automates "normaux"? Je ne comprends pas trop. Merci !
Merci de m'avoir communiqué le sujet.
Si j'ai bien compris, quand tu dessines un automate boustrophédon, tu mets toujours les flèches que tu mets pour un automate "normal". Simplement, à chaque transition (donc à chaque "flèche normale" qui est surmontée d'un élément de l'alphabet), tu indiques une petite flèche qui va soit vers la gauche soit vers la droite. 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).

(d'abord tu ajoutes a par la transition (a, <---) puis par la transition (b, ---->) tu ajoutes b à la fin de ton mot ce qui fait ab puis par la transition (b, <-----) tu ajoutes b au début de ton mot ce qui fait bab).

C'est comme ça que je comprends la phrase "La capacité supplémentaire d’un automate boustrophédon par rapport à un automate
fini classique, est de pouvoir se déplacer sur le mot vers la droite et la gauche (là où un
automate fini ne peut qu’avancer vers la droite)."

Désolé pour le schéma un peu moyen.


wow je suis vraiment désolé, je pensais avoir répondu et là en voulant faire un tour je remarque que pas du tout ! c'est vraiment la honte... j'en suis vraiment désolé
je voulais te remercier pour tes explications, je n'avais pas du tout compris la chose comme ça mais grâce à toi j'ai bien compris maintenant !!! (et le schéma était très clair, je t'en remercie)
j'avais vu tes explications le jour même, ça m'a permis de comprendre et d'avancer dans le problème par la même occasion, mais visiblement je ne t'ai même pas répondu... ça ne se fait pas
bref, un grand merci à toi pour ton aide et tes explications, c'est devenu franchement plus clair !

Répondre