Discussion :

[salah1]

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

Voici l'énoncé :

On définit un automate par A = (Q, q0, F, A, R), tels que :
 Q est un ensemble finit d'états ;
 q0 ε Q est l'état initial de l’automate ;
 F ε Q est l'ensemble des états finaux de l’automate;
 A est un ensemble fini d’étiquettes ou alphapbets;
 R ⊆ Q x A x Q est une relation de transition. Chaque transition (q, a, q’ ) ε R
représente une transition d'un état source q vers un autre état cible q’, suite à
l'activiation de la lettre a.
Travail demandé :
1. Implémenter le prédicat automate en prolog et illustrez votre proposition avec une base de
faits de votre choix.
2. Donnez des requêtes d’interrogation de votre prédicat : recherche de l’état initial,
vérification si un état est final ou non, existence d’une transtion particulière... ?
3. Pour améliorer le prédicat automate, on considère que les états de l’automate sont de troix
types (initial, final et intermédiaire). La nouvelle spécification de l’automate devient :
automate (états, alphabet, transitions). Implémenter la nouveau prédicat automate.
4. Dans un automate, on définit un chemin par une combinaison finie d’états et des lettres de
l’alphabet de cet automate: c= q0.a0.q1.a1...qn.an.qn+1. Un chemin est dit complet s’il
commence par un état intial et il se termine à un état final ; c'est-à-dire si qn+1 ε F.
Donnez le prédicat chemin_complet qui permet de construire tous les chemins complets
d’un automate. (entrées : la base des faits + prédicat automate, sortie: liste des chemins
complets).
5. A partir du chemin complet on extrait les mots exprimant uniquement la séquence des
noms des transitions (c'est-à-dire les lettres de l’alphabet). On peut voir un mot de
l’automate comme une liste de lettres de l’alphabet.
Implémenter un prédicat déterminant si un mot est reconnu par un automate. Un mot est
reconnu par l’automate s’il commence par un état initial et se termine à un état final.
Testez votre prédicat avec la base des faits de la question 1.
6. Améliorer vos prédicats afin de pouvoir tester si l’automate est déterministe.
NB : Un automate est détreministe si à partir d’un état q ne peut sortir qu’une transition
unique de nom a. Dans ce cas, les transitions à partir de chaque état sont déterminées de
façon unique par le symbole d'entrée.

[Trap D]

Il faut montrer ce qui a déjà été écrit pour qu'on puisse aider.

[salah1]

1er prd pour mon mauvais niveau en français
je testé avec la premier question

Implémenter le prédicat automate en prolog et illustrez votre proposition avec une base de faits de votre choix.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
automate(Q,QQ,F,A,R):-
    Q =[1,2,3,4],       %les etats
    QQ = [1],             %l'etat initial 
    F = [3,4],              %les etat finaux
    A  =[a,b,c],           %mon  alphapbets  
    R =[[1,a,1],[1,b,2],[1,c,4],[2,b,4],[2,a,1],[2,c,3],[3,b,3],[3,a,4],[3,c,2],[4,a,4],[4,b,1],[4,c,3]].   %les transition

et pour les requêtes d’interrogation normalement semple

automate(Q,QQ,F,A,R).
set requetes donner tout les réponse

en suit l'amélioration

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
automate(E,A,R):-
    E=[[1],[3,4],[2]],
    A =[a,b,c],
    R =[[1,a,1],[1,b,2],[1,c,4],[2,b,4],[2,a,1],[2,c,3],[3,b,3],[3,a,4],[3,c,2],[4,a,4],[4,b,1],[4,c,3]].

ici je trouve la difficulté dans les chemins.

[salah1]

Il faut montrer ce qui a déjà été écrit pour qu'on puisse aider.

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
 
chemin_complet:-automate(Q,QQ,_,A,R),
	member(Qq,QQ),
	member(E,Q),
	member(X,A),
	member([Qq,X,E],R),
	writeln([Qq,X,E]),
	chemin_complet(E).
%%dans le cas où la liste est vide
chemin_complet:-automate(_,QQ,F,_,_),
	member(E,QQ),
	member(E,F).
%%le parcours des états  intermédiaire
chemin_complet(E):-automate(Q,_,_,A,R),
	member(EE,Q),
	member(X,A),
	member([E,X,EE],R),
	writeln([E,X,EE]),
	chemin_complet(EE).
%%l'etat final
chemin_complet(E):-automate(_,_,F,_,_),
	member(E,F),
	writeln('____________________').

je testé ce code mais je trouve des fautes a l’exécution

[Trap D]

Quelles sont ces fautes ?
Il faut avoir une batterie de tests : les inputs et les outputs attendus.
Vous pensez être à quel stade de votre énoncé.

[salah1]

Quelles sont ces fautes ?
Il faut avoir une batterie de tests : les inputs et les outputs attendus.
Vous pensez être à quel stade de votre énoncé.

l’échec est au niveau de résulta example 2 n'est pas état initial

l’échec est au niveau de résulta example 2 n'est pas état initial

[Trap D]

Bonjour
J'ai réécrit l'automate en prenant votre graphe et en supposant que 1 est le seul état d'entrée :

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
27
28
29
30
31
32
33
34
automate(E,A,R):-
    E=[[1],[3,5],[2,4]],
    A =[a,b,c],
    R =[[1,a,2],[1,b,3],
        [2,b,3],[2,a,4],
        [3,b,5],
        [4,b,3],[4,a,5]].
 
etat_initial(X) :-
    automate([Q, _, _], _ ,_),
    member(X,Q).
 
etat_final(X) :-
    automate([_, F, _], _ ,_),
    member(X, F).
 
transition(X, Y, [X,A,Y]) :-
    automate(_, _ , R),
    member([X, A, Y], R).
 
 
chemin(X,Y,[C]) :-
    transition(X,Y,C).
 
chemin(X,Y,[[C1]|C2]) :-
    transition(X,Z,C1),
    chemin(Z,Y,C2).
 
 
chemin_complet(C):-
        automate([Q,F,_],_,_),
	member(X,Q),
	member(Y,F),
        chemin(X,Y,C).

J'obtiens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
?- chemin_complet(C).
C = [[1, b, 3]] ;
C = [[1, a, 2], [2, b, 3]] ;
C = [[1, a, 2], [2, a, 4], [4, b, 3]] ;
C = [[1, a, 2], [2, b, 3], [3, b, 5]] ;
C = [[1, a, 2], [2, a, 4], [4, a, 5]] ;
C = [[1, a, 2], [2, a, 4], [4, b, 3], [3, b, 5]] ;
C = [[1, b, 3], [3, b, 5]] ;
false.

Attention, il y a un piège potentiel dans ce code, il n'est pas applicable à tous les graphes !

[salah1]

merci beaucoup
je travailler aussi sur un code

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
 
chemin_complet:-automate(Q,QQ,_,A,R),
	member(Qq,QQ),
	member(E,Q),
	member(X,A),
	member([Qq,X,E],R),
	L=[[Qq,X,E]],
	chemin_complet(E,L).
%%dans le cas où la liste est vide
chemin_complet:-automate(_,QQ,F,_,_),
	member(E,QQ),
	member(E,F).
%%le parcours des états  intermédiaire
chemin_complet(E,L):-automate(Q,_,_,A,R),
	member(EE,Q),
	member(X,A),
	member([E,X,EE],R),
	L1=[L,[E,X,EE]],
	chemin_complet(EE,L1).
%%l'etat final
chemin_complet(E,L):-automate(_,_,F,_,_),
	member(E,F),
	writeln(L).

mais je veux utiliser voter code

merci merci