IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Prolog Discussion :

SWI-Prolog : Représentation d'automates à états finis


Sujet :

Prolog

  1. #1
    Membre régulier Avatar de nAKAZZ
    Homme Profil pro
    Développeur .Net / Labo de génétique
    Inscrit en
    Décembre 2014
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur .Net / Labo de génétique

    Informations forums :
    Inscription : Décembre 2014
    Messages : 32
    Points : 122
    Points
    122
    Par défaut SWI-Prolog : Représentation d'automates à états finis
    Bonjour à tous,

    J'ai commencé le prolog il y a quelques semaines et j'ai des difficultés sur un exercice.

    Voici l'énoncé :
    Nous nous intéressons à la manipulation des automates à états finis reconnaissant des langages rationnels.

    On défini un automate par :
    - un alphabet (ALPHABET)
    - un ensemble d’états (ETATS)
    - un ensemble de transitions (TRANSITIONS)
    - un ensemble d’états initiaux (INITIAUX)
    - un ensemble d’états finaux (FINAUX).

    Un automate pourra donc être représenté par :
    automate(ALPHABET, ETATS, TRANSITIONS, INITIAUX, FINAUX)

    Par ailleurs chaque état et chaque transition peuvent être représentés par un prédicat :
    etat(UnEtat)
    transition(UnEtatDepart,UneLettre, UnEtatArrivee)

    Questions

    > Implémenter un prédicat déterminant si un mot est reconnu par un automate. Tous deux donnés.
    estReconnu(+UnMot,+UnAutomate)

    Note : on peut voir un mot comme une liste de lettres.

    > Implémenter un prédicat déterminisant un automate donné
    determiniser(+UnAutomate,-UnAutomateEquivalentDeterministe)
    Mon problème majeur est que je ne vois absolument pas comment commencer ce problème (notamment au niveau de la représentation de l'automate).

  2. #2
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    C'est à vous de présenter quelques éléments Prolog, on ne fait pas les devoirs.

    "A la main", comment représenteriez vous l'automate ????
    Prenez un exemple d'automate simple, et faites les manipulations de cet automate, que faut-il avoir comme données, comme variables ?
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  3. #3
    Membre régulier Avatar de nAKAZZ
    Homme Profil pro
    Développeur .Net / Labo de génétique
    Inscrit en
    Décembre 2014
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur .Net / Labo de génétique

    Informations forums :
    Inscription : Décembre 2014
    Messages : 32
    Points : 122
    Points
    122
    Par défaut
    En prenant un automate simple sur l'alphabet { a, b } défini par un état de sortie (2) et un état d'entrée (0).
    Je lui ai associé 4 transitions :
    0 -a-> 1
    0 -b > 2
    1 -a-> 2
    1 -b-> 0

    L'expression rationnelle dénotant cet automate est donc de la forme : E(a, b) = (a.b)*.(a²+b)

    Comme je l'ai dit, mon soucis n'est absolument pas au niveau des automates mais vraiment au niveau de la syntaxe à utiliser en Prolog.
    Je suis un habitué du C/C++, Java et je me perds un peu avec ce langage qui change vraiment de la programmation séquentielle.

    Du coup, j'aurais envie de le représenter via ces faits en prolog :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    automate([a, b], [0, 1, 2], [[0, a ,1], [0, b, 2], [1, a, 2], [1, b, 0]], [0], [2]).
     
    etat(0).
    etat(1).
    etat(2).
     
    transition(0, a, 1).
    transition(0, b, 2).
    transition(1, a, 2).
    transition(1, b, 0).
    Mais ça me paraît "mauvais" et je ne vois pas comment exploiter ça.

    Les exercices précédant celui-ci étaient nettement plus simples avec des questions du type intersection, union, différence d'ensembles. Là on part dans quelque chose de nettement plus complexe et je bloque totalement.

    D'ailleurs, avant de réaliser la fonction "estReconnu" permettant de vérifier si un mot peut justement être reconnu par l'automate, il me semblait plus logique de commencer par déterminiser cet automate afin de simplifier le travail de la première fonction.

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    D'après moi, je ne suis pas votre prof, vous n'en êtes pas loin :
    L'automate peut être défini ainsi :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    	Automate = automate([a, b],  % <== l'alphabet
    			    [etat(0), etat(1), etat(2)], % <== ETATS
    			    [transition(0, a ,1), transition(0, b, 2), transition(1, a, 2), transition(1, b, 0)], % <==  TRANSITIONS
    			    [etat(0)], % <==  INITIAUX
    			    [etat(2)]). % <== FINAUX
    Pour la reconnaissance d'un mot, on peut faire ainsi pour le lancement de la reconnaissance
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    estReconnu([H | Tail],UnAutomate):-
    	% on reprend la définition de l'automate
    	UnAutomate = automate(ALPHABET, ETATS, TRANSITIONS, INITIAUX, FINAUX),
    	% pour commencer, il faut un etat initial
    	member(etat(Initial), INITIAUX),
    	% un etat possible de l'automate
    	member(etat(E), ETATS),
    	% et que la transition existe
    	member(transition(Initial, H, E), TRANSITIONS),
    	% on lance maintenant la reconnaissance
    	estReconnu(Tail, E, UnAutomate).
    A vous d'écrire le prédicat estReconnu/3 dans le cas général et dans le cas de succés de reconnaissance.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  5. #5
    Membre régulier Avatar de nAKAZZ
    Homme Profil pro
    Développeur .Net / Labo de génétique
    Inscrit en
    Décembre 2014
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur .Net / Labo de génétique

    Informations forums :
    Inscription : Décembre 2014
    Messages : 32
    Points : 122
    Points
    122
    Par défaut
    Merci pour ces conseils.
    En essayant de les suivre, j'en arrive à ceci :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    estReconnu([H | Tail], E, UnAutomate):-
    	UnAutomate = automate(_, ETATS, TRANSITIONS, _, _),
    	member(etat(S), ETATS),
    	member(transition(E, H, S), TRANSITIONS),
    	estReconnu(Tail, S, UnAutomate).
     
    estReconnu([H | []], E, UnAutomate):-
    	UnAutomate = automate(_, _, TRANSITIONS, _, FINAUX),
    	member(etat(F), FINAUX),
    	member(transition(E, H, F), TRANSITIONS).
     
    % Cas particuliers du mot vide et du mot d'une lettre
    estReconnu([X], UnAutomate):-
    	UnAutomate = automate(_, _, TRANSITIONS, INITIAUX, FINAUX),
    	member(etat(I), INITIAUX),
    	member(etat(F), FINAUX),
    	member(transition(I, X, F), TRANSITIONS).
     
    estReconnu([], UnAutomate):-
    	UnAutomate = automate(_, _, _, INITIAUX, FINAUX),
    	member(etat(E), INITIAUX),
    	member(etat(E), FINAUX).
    J'ai essayé sur quelques mots reconnus (ou pas) par l'automate et ça me semble fonctionner.
    Cela vous semble-t-il correct ?

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Ce n'est pas mal du tout, vous pouvez simplifier le code en considérant le mot vide en fin de reconnaissance :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    estReconnu([H | Tail],UnAutomate):-
    	UnAutomate = automate(_ALPHABET, ETATS, TRANSITIONS, INITIAUX, _FINAUX),
    	member(etat(Initial), INITIAUX),
    	member(etat(E), ETATS),
    	member(transition(Initial, H, E), TRANSITIONS),
    	estReconnu(Tail, E, UnAutomate).
     
    % cas particulier du mot vide
    estReconnu([], UnAutomate):-
    	UnAutomate = automate(_, _, _, INITIAUX, FINAUX),
    	member(etat(E), INITIAUX),
    	member(etat(E), FINAUX).
     
    % reconnaissance "générale" du mot
    estReconnu([H | Tail], E, UnAutomate):-
    	UnAutomate = automate(_, ETATS, TRANSITIONS, _, _),
    	member(etat(S), ETATS),
    	member(transition(E, H, S), TRANSITIONS),
    	estReconnu(Tail, S, UnAutomate).
     
    % fin de reconnaissance
    % il n'y a plus de lettres
    % et on est dans un état final
    estReconnu([], E, UnAutomate):-
    	UnAutomate = automate(_, _, _TRANSITIONS, _, FINAUX),
    	member(etat(E), FINAUX).
    je remarque qu'on n'a pas testé que les lettres appartebaient à l'alphabet, c'est implicitement fait au moment des transitions.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  7. #7
    Membre régulier Avatar de nAKAZZ
    Homme Profil pro
    Développeur .Net / Labo de génétique
    Inscrit en
    Décembre 2014
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur .Net / Labo de génétique

    Informations forums :
    Inscription : Décembre 2014
    Messages : 32
    Points : 122
    Points
    122
    Par défaut
    Citation Envoyé par Trap D Voir le message
    Ce n'est pas mal du tout, vous pouvez simplifier le code en considérant le mot vide en fin de reconnaissance :
    (...)
    je remarque qu'on n'a pas testé que les lettres appartenaient à l'alphabet, c'est implicitement fait au moment des transitions.
    Merci pour l'optimisation.

    Pour ce qui est de la vérification de l'appartenance des lettres à l'alphabet, je l'avais ajoutée avant de la retirer en pensant que, comme vous le dites, c'était indirectement vérifié au moment du test des transitions.

    Me reste donc à terminer le prédicat determiniser/2.
    Je passerai à nouveau ici s'il me pose problème.

    En tout cas merci pour vos conseils, je commence à mieux saisir le fonctionnement du langage.

  8. #8
    Nouveau membre du Club
    Homme Profil pro
    L3 informatique
    Inscrit en
    Mars 2013
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : L3 informatique

    Informations forums :
    Inscription : Mars 2013
    Messages : 21
    Points : 26
    Points
    26
    Par défaut
    Bon, je répond un peu tard, mais voici ce que j'ai fait pour cet exercice. Vu que apparemment tu as déjà réussi à la faire, je peux donc mettre directement ma réponse ici :

    Code prolog : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
    estReconnu([],Automate):-initial(I,Automate),estFinal(I,Automate). %estReconnu/2
    estReconnu([Lettre|Mot],Automate):-initial(I,Automate),ecrire(Lettre,Automate,I,F),estReconnu(Mot,Automate,F).
     
    %estReconnu/3
    estReconnu([Lettre|Mot],Automate,Etat):-ecrire(Lettre,Automate,Etat,F),estReconnu(Mot,Automate,F).
    estReconnu([],Automate,Etat):-estFinal(Etat,Automate). 
     
    initial(Etat,automate(_,_,_,I,_)):-member(Etat,I). %initial/2
     
    estFinal(Etat,automate(_,_,_,_,F)):-member(Etat,F). %estFinal/2
     
    ecrire(Lettre,automate(_,_,T,_,_),I,F):-member(transition(I,Lettre,F),T). %ecrire/4
    Par contre je n'ai pas réussi à rendre un automate déterministe.

    Pour les tests j'ai testé avec cet automate :
    Nom : automate.PNG
Affichages : 1497
Taille : 3,8 Ko

    Exemple de sortie :
    Nom : prolog_automate.png
Affichages : 1590
Taille : 29,8 Ko

    P.S : Si tu veux plus de détail sur l'execution utilise le prédicat déjà défini : trace/0 , et pour quitter cela, utilise la prédicat notrace/0 suivi du prédicat nodebug/0

  9. #9
    Futur Membre du Club
    Homme Profil pro
    si
    Inscrit en
    Décembre 2017
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : Algérie

    Informations professionnelles :
    Activité : si
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2017
    Messages : 6
    Points : 5
    Points
    5
    Par défaut bns se code ne marche pas aide moi s.v.p
    automate(Q,QQ,F,A,R):-Q is [etat(1),etat(2),etat(3),etat(4)],QQ is [etat(1)],F is [etat(3),etat(4)],A is[a,b,c],R is [transition(1,a,1),transition(1,b,2),transition(1,c,4),transition(2,b,4),transition(2,a,1),transition(2,c,3),transition(3,b,3),transition(3,a,4),transition(3,c,2),transition(4,a,4),transition(4,b,1),transition(4,c,3)].

Discussions similaires

  1. [Etat-Transition] Relation avec les automates d'état finis vu en théorie des langages ?
    Par isma44 dans le forum Autres Diagrammes
    Réponses: 3
    Dernier message: 15/03/2007, 01h15
  2. Le mode debug de swi-prolog
    Par Boubou Balrog dans le forum Prolog
    Réponses: 2
    Dernier message: 18/12/2006, 11h55
  3. Désactiver les warnings en swi-prolog
    Par Cecilka dans le forum Prolog
    Réponses: 2
    Dernier message: 15/12/2006, 12h33
  4. theorie de langages : automate à etat fini
    Par Miss_Miss dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 13/06/2006, 21h46
  5. Réponses: 3
    Dernier message: 03/05/2006, 16h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo