Automate fini

[CygneBlanc]

Bonjour,

Je suis face à une question qui n'est pas très claire pour moi. Je souhaiterai avoir votre avis.

"On souhaite reconnaître l'ensemble des mots sur l'alphabet {a,b} qui terminent par le motif aba. Ce langage contient par exemple les mots aba, abbbaba, ababa, mais pas les mots ab, abab ou bba.Décrire l’automate (avec le nombre minimal d’états) qui reconnait ce langage. Combien d’états possède t-il ? Quel est le nombre de transition retournant dans l’état initial (depuis n’importe quel autre état)."

Je n'arrive pas à répondre à cette question car je n'ai pas de schéma pour au moins déterminer le type d'automate et déterminer toutes ces caractéristiques (états initial, états, transitions).


Je vous remercie de votre compréhension.

Bien à vous,

Cygne Blanc
-----

[pm42]

Si on te demande de faire un automate qui reconnait tous les mots qui se terminent par a, tu sais faire ?

[CygneBlanc]

Non je ne sais pas faire.

[pm42]

Non je ne sais pas faire.

Tu sais faire quoi comme automate ? Parce que l'idée du forum, c'est qu'on t'aide si tu montres ce que tu as déjà fait.
Par exemple, pour faire celui qui détecte les fins en a, quelles sont les transitions juste après le point d'entrée ?
En gros, je te donne un caractère, tu fais quoi si c'est un a et quoi si ce n'est pas un a ?

[A voir en vidéo sur Futura]

[CygneBlanc]

"Parce que l'idée du forum, c'est qu'on t'aide si tu montres ce que tu as déjà fait." Entièrement d'accord avec vous. Mais je ne comprends du tout la question, est-ce que on me demande de dessiner un automate ?

C'est la première fois que j'ai à faire ce genre de consigne et j'ai pour habitude d'avoir un schéma d'un automate.
Mes cours et mes exercices ne m'aident pas à répondre à vos questions et cette question.

[pm42]

C'est la première fois que j'ai à faire ce genre de consigne et j'ai pour habitude d'avoir un schéma d'un automate.

Si tu as pour habitude d'avoir une schéma, tu ne peux pas en dessiner un ? En adapter un ?

[CygneBlanc]

Je ne vais pas abuser de votre temps, je vais bien le travailler de mon coté et tenter d'avoir un schéma et si je ne trouve vraiment pas. Je reviendrais vers vous demain après-midi. Merci pour investissement et votre gentillesse.

[invite40cf7093]

Salut Cygne Blanc,

il y a quelque questions que je ne comprend pas. mais sinon ça me parait assez simple

Je vais t'expliquer la façon algorithmique en python que je pense peut fonctionner dessus.

Tu devras utiliser soit une librarie text mining, ou plus simple un split pour chaque espace.

Tu fais une boucle for pour chaque mot dans le text

Tu fais un Tuple et pas une liste ( qui te permet d'avoir une valeur unique ) dans lequel tu ajoute le mot (IF ) condition que le Mot[:-3] ( en gros les 3 dernier caractère du mots ) = "aba"

Salut,

[pm42]

il y a quelque questions que je ne comprend pas. mais sinon ça me parait assez simple

Peut-être que le fait de de ne pas comprendre certaines choses est un bon indicateur que ce n'est pas si simple ?

Je vais t'expliquer la façon algorithmique en python que je pense peut fonctionner dessus.

Cela peut fonctionner sur tous les langages, même pas besoin qu'ils soient turing-complets, c'est dire.

Tu devras utiliser soit une librarie text mining, ou plus simple un split pour chaque espace.

Absolument pas, cela n'a rien à voir. On parle d'automates à états finis, sujet classique, bien décrit théoriquement, ancien et n'ayant aucun lien avec le text mining.
Dans ce contexte "mot" a un sens un peu différent et le caractère espace n'en fait pas partie.

Tu fais un Tuple et pas une liste ( qui te permet d'avoir une valeur unique ) dans lequel tu ajoute le mot (IF ) condition que le Mot[:-3] ( en gros les 3 dernier caractère du mots ) = "aba"

Si c'était pour faire cela, on utiliserait les fonctions standard de python et il y a beaucoup mieux que les boucles for, les [:-3] : tout s'écrit est une ligne avec split, endswith et une list comprehension ou un map/filter (qui sont équivalent)...

Mais encore une fois, ce n'est pas du tout le sujet : https://fr.wikipedia.org/wiki/Automate_fini

[CygneBlanc]

Bonjour,

J'ai tenté d'en dessiner mais il n'est pas vraiment complet(je me suis aidé d'un exemple présenté en cours en pièce jointe). J'ai du mal à faire les transitions mais normalement il y en a 2 pour la lettre b et a. J'a i réussi à repérer l’état initial, les états, les lettres {a,b} et les états acceptants qui sont: aba, abbbaba, ababa et ab, abab ou bba il y en a 6 au total.

[CygneBlanc]

J 'aurai pensé à ce que cet exemple pourrait bien représenter mon cas sauf qu'à la place des chiffres. 1 sur le carré bleu= a sans la boucle et 1,0 = b et le 0 sur le carré vert = b avec la boucle.

[pm42]

J'ai tenté d'en dessiner mais il n'est pas vraiment complet.

C'est pas mal pour un début. Plusieurs choses : ton alphabet tel qu'indiqué dans l'énoncé est { a, b }. Donc pas la peine de prendre en compte des c et d : ils n'existent pas.

Ensuite, on va dire qu'on est dans l'état d'entrée : on recoit un b. Qu'est ce qu'on fait ? On revient au même point.

On reçoit un a => on va dans l'état "commence par a". Dans cet état, on reçoit un autre a. Qu'est ce qu'on fait ? On revient sur l'état "commence par a".
Mais si on a reçu un b, on va dans l'état "commence par ab".

Est ce que tu vois la logique ?
Le 1er état/transitions va virer tous les b au début. Puis dès qu'on a un a, on va passer dans un état où on regarde si on a un b ensuite...

Le dernier état est atteint si on a eu aba et là, on regarde "est ce qu'on a une fin de mot ?". Si oui on sort. Sinon, on revient à l'état "j'ai reçu un a".

En complétant les étapes intermédiaires, tu dois pouvoir faire ton graphe.

[CygneBlanc]

Je comprends mais est-il possible de montrer votre schéma, une explication via une image serait plus rapide et limpide s'il vous plait ?

[pm42]

Je comprends mais est-il possible de montrer votre schéma, une explication via une image serait plus rapide et limpide s'il vous plait ?

Si j'ai le temps, j'ai pas mal de boulot cet après-midi.

[CygneBlanc]

Bien sur, je vous remercie.

Je vous souhaite une bonne organisation.