Discussion :

[wallace27]

Bonjour,

Au plan purement théorique, est-ce que quelqu'un réussirait à m'expliquer comment il est possible de déterminer que oui ou non la partie du texte est reconnue dans les exemples d'appels ci-dessous ?







Un grand merci pour votre aide précieuse.

[Trap D]

Bonjour

Sur l'écriture simplifiée s([a|S2], R] := s(S2, [b|R]). on voit que autant de a que de b sont consommés pour la simplification de l'expression et la création de R.
Ce qui veut dire qu'il y a autant de a que de b consommés et que le reste se retrouve dans R.
On remarque aussi qu'il faut au minimum une paire [a,b] testée s([a,b], []). donne Yes mais s([], R). donne False.
Je ne sais pas si c'est très théorique mais c'est ce qu'on voit lorsqu'on détaille le prédicat s.

[wallace27]

Merci,

Comment passe-t-on de :

Code :

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

S → a S b | ɛ

à :

Code :

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

s([a|S2],R) :- s(S2,[b|R]).

Quelles sont exactement les étapes qui permettent d'atteindre ce résultat ? L'idée serait que je puisse appliquer le raisonnement et le déploiement des opérations en question de manière systématique afin de pouvoir résoudre tous les cas.

Merci pour votre aide.

[Trap D]

le code s -> a S b | ɛ s'écrit en DCG :

Code :

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

1
2
s --> [].
s --> [a], s,[b].

On obtient alors l'écriture

Code :

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

1
2
3
4
5
 ? :- listing(s)
s(A, A).
s([a|A], C) :-
        s(A, B),
        B=[b|C].

[wallace27]

Merci,

dans cette formule :

Code :

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

1
2
3
4
5
 ? :- listing(s)
s(A, A).
s([a|A], C) :-
        s(A, B),
        B=[b|C].

que représente exactement le "A" majuscule ?

[Trap D]

Une liste qui peut éventuellement être vide

[wallace27]

mais cette liste qui peut éventuellement être vide, si elle n'est pas vide, alors elle ne peut être que ab ou aabb ou aaabbb ou asb. C'est bien juste ?

[Trap D]

Non, elle peut contenir n'importe quoi, mais si c'est n'importe qoi, elle se retrouvera dans R.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 ?- s([a,c], R).
R = [a,c] ;
false.
 
 ?- s([b,c,s], R).
R = [b,c,s] ;
false.
 
 ?- s([a,b], R).
R = [a,b] ;
R = [] ;
false.

[wallace27]

Ok parfait merci. Dernière chose, si je n'ai pas accès à une machine et que je ne peux donc pas taper la commande listing, comment puis-je procéder pour passer de :

Code :

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

S → a S b | ɛ

à :

Code :

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

s([a|S2],R) :- s(S2,[b|R]).

Est-ce qu'il existe une méthode que je pourrais suivre à la lettre ?

[Trap D]

Elle existe sans doute, mais j'avoue ne pas la connaître.