automate bi-directionnel
automate bi-directionnel
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)
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)
Re: automate bi-directionnel
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).
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)
Re: automate bi-directionnel
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
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
Re: automate bi-directionnel
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
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)
Re: automate bi-directionnel
Bonjour,
Si tu communiques le sujet, je veux bien essayer de t'aider. Sinon, je ne pense pas que je pourrai vraiment.
Si tu communiques le sujet, je veux bien essayer de t'aider. Sinon, je ne pense pas que je pourrai vraiment.
Re: automate bi-directionnel
Merci beaucoup pour vos réponses (j'ai dû recréer mon compte car mon mot de passe ne marchait plus...).
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 !
@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 !
Re: automate bi-directionnel (cours de L3 ENS Lyon !!)
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:
« 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)
Re: automate bi-directionnel
@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.
Re: automate bi-directionnel
Merci de m'avoir communiqué le sujet.clemparc2 a écrit : ↑15 nov. 2021 16:12Merci beaucoup pour vos réponses (j'ai dû recréer mon compte car mon mot de passe ne marchait plus...).
@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 !
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.
Re: automate bi-directionnel
Inversion a écrit : ↑15 nov. 2021 17:34Merci de m'avoir communiqué le sujet.clemparc2 a écrit : ↑15 nov. 2021 16:12Merci beaucoup pour vos réponses (j'ai dû recréer mon compte car mon mot de passe ne marchait plus...).
@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 !
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 !