Automate fini
Répondre à la discussion
Affichage des résultats 1 à 15 sur 15

Automate fini



  1. #1
    CygneBlanc

    Automate fini


    ------

    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

    -----

  2. #2
    pm42

    Re : Automate fini

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

  3. #3
    CygneBlanc

    Re : Automate fini

    Non je ne sais pas faire.

  4. #4
    pm42

    Re : Automate fini

    Citation Envoyé par CygneBlanc Voir le message
    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 ?

  5. A voir en vidéo sur Futura
  6. #5
    CygneBlanc

    Re : Automate fini

    "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.
    Dernière modification par CygneBlanc ; 07/01/2021 à 19h37.

  7. #6
    pm42

    Re : Automate fini

    Citation Envoyé par CygneBlanc Voir le message
    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 ?

  8. #7
    CygneBlanc

    Re : Automate fini

    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.

  9. #8
    Totolinconnu971

    Re : Automate fini

    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,

  10. #9
    pm42

    Re : Automate fini

    Citation Envoyé par Totolinconnu971 Voir le message
    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 ?

    Citation Envoyé par Totolinconnu971 Voir le message
    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.

    Citation Envoyé par Totolinconnu971 Voir le message
    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.


    Citation Envoyé par Totolinconnu971 Voir le message
    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

  11. #10
    CygneBlanc

    Re : Automate fini

    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 jointeNom : automate fini forum.png
Affichages : 266
Taille : 73,2 Ko). 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.

  12. #11
    CygneBlanc

    Re : Automate fini

    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.Nom : automat fini forum informatqiue.png
Affichages : 149
Taille : 8,9 Ko

  13. #12
    pm42

    Re : Automate fini

    Citation Envoyé par CygneBlanc Voir le message
    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.

  14. #13
    CygneBlanc

    Re : Automate fini

    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 ?

  15. #14
    pm42

    Re : Automate fini

    Citation Envoyé par CygneBlanc Voir le message
    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.

  16. #15
    CygneBlanc

    Re : Automate fini

    Bien sur, je vous remercie.

    Je vous souhaite une bonne organisation.

Discussions similaires

  1. système ITE Pré-fini ou fini
    Par Ritch4533 dans le forum Habitat bioclimatique, isolation et chauffage
    Réponses: 3
    Dernier message: 26/06/2018, 15h34
  2. [Autre] Relais entre une sortie automate et une entrée automate
    Par Antho49 dans le forum Électronique
    Réponses: 7
    Dernier message: 29/06/2016, 11h48
  3. TPE fini
    Par invited1c8361c dans le forum TPE / TIPE et autres travaux
    Réponses: 1
    Dernier message: 11/02/2007, 18h11
  4. Univers Fini/Infini et matière Fini?
    Par dewsz dans le forum Archives
    Réponses: 6
    Dernier message: 15/12/2006, 16h46