En savoir plus sur Prolog! Exemple de pratique DCG

Question

J'ai progressé à travers Learn Prolog Now! en tant qu'étude personnelle et j'apprends maintenant sur les Grammaires à Clause Définie. J'ai quelques difficultés avec l'une des tâches de la session pratique. The task lit:

Le langage formel un ⁿ b ^2m c ^2m d ⁿ est constitué de toutes les chaînes de la forme suivante: un bloc ininterrompu de un s suivi d'un bloc ininterrompu de b s suivies d'un bloc ininterrompu de c s suivi d'un bloc ininterrompu de d s, de telle sorte que la un et d 012.303.blocs sont exactement la même longueur, et les c et d blocs sont également exactement la même longueur et, en outre constitués d'un nombre pair de c s et d s respectivement. Par exemple, & epsilon;, abbccd et aaabbbbccccddd appartiennent tous à une ⁿ b ^{2m 2m c} d ^{n. Ecrire un DCG qui génère ce langage.}

Je suis capable d'écrire des règles qui génèrent un ⁿ d ⁿ, b ^2m c ^2m, et même un ⁿ b ^2m et c ^2m d ⁿ ... mais je n'arrive pas à joindre toutes ces règles dans un ⁿ b ^2m c ^2m d ⁿ. Voici les règles qui peuvent générer un ⁿ d ⁿ et b ^2m c ^2m.

s1 --> []. 
s1 --> a,s1,d. 
a --> [a]. 
d --> [d]. 

s2 --> []. 
s2 --> c,c,s2,d,d. 
c --> [c]. 
d --> [d]. 

Est-ce un ⁿ b ^2m c ^2m d ⁿ vraiment un CFG, et est-il possible d'écrire un DCG en utilisant seulement ce qui a été enseigné dans la leçon (pas d'arguments supplémentaires ou le code , etc)? Si oui, quelqu'un peut-il m'offrir quelques conseils sur la façon dont je peux me joindre à eux pour que je puisse résoudre la tâche donnée?

Answer 1

@Timothy, votre réponse fonctionne, mais il génère des doublons:

?- length(S,_), s(S,[]). 
S = [] ; 
S = [a, d] ; 
S = [a, d] ;   % XXX 
S = [b, b, c, c] ; 
S = [a, a, d, d] ; 
S = [a, a, d, d] ;  % XXX 

Cela peut être fixé en supprimant une clause, laissant le DCG:

s --> x. 
s --> a,s,d. 

x --> []. 
x --> b,b,x,c,c. 

% a, b, c, d the same 

Cela génère:

?- length(S,_), s(S,[]). 
S = [] ; 
S = [a, d] ; 
S = [b, b, c, c] ; 
S = [a, a, d, d] ; 
S = [a, b, b, c, c, d] ; 
S = [a, a, a, d, d, d] ; 
S = [b, b, b, b, c, c, c, c] ; 
S = [a, a, b, b, c, c, d, d] ; 
S = [a, a, a, a, d, d, d, d] ; 

Answer 2

Que diriez-vous quelque chose comme:

n(L,N) --> n(L,N,0). 

n(_,N,N) --> [], !. 
n(L,N,K) --> L, {K1 is K + 1}, n(L, N, K1). 

abbccd(N,M) --> 
    {M1 is 2*M}, 
    n("a",N), 
    n("b",M1), 
    n("c",M1), 
    n("d",N). 

gen :- 
    forall((
      between(1,4,N), 
     between(1,4,M), 
     phrase(abbccd(N,M),S), 
     string_to_atom(S,A) 
      ), 
      writeln(A)). 

exécution:

?- gen. 
abbccd 
abbbbccccd 
abbbbbbccccccd 
abbbbbbbbccccccccd 
aabbccdd 
aabbbbccccdd 
aabbbbbbccccccdd 
aabbbbbbbbccccccccdd 
aaabbccddd 
aaabbbbccccddd 
aaabbbbbbccccccddd 
aaabbbbbbbbccccccccddd 
aaaabbccdddd 
aaaabbbbccccdddd 
aaaabbbbbbccccccdddd 
aaaabbbbbbbbccccccccdddd 
true. 

Answer 3

Je crois que j'ai tout compris ...

s --> x. 
s --> a,d. 
s --> a,s,d. 

x --> []. 
x --> b,b,x,c,c. 

a --> [a]. 
b --> [b]. 
c --> [c]. 
d --> [d]. 

?- s([],[]). 
Yes 

?- s([a,b,c,c,d],[]). 
No 

?- s([a,a,a,b,b,c,c,d,d,d],[]). 
Yes 

Il est amusant de regarder la solution et de penser, « Je creusais mon cerveau sur que? » Mais je suppose que c'est la moitié du plaisir d'apprendre quelque chose de nouveau, surtout quand c'est quelque chose comme la programmation logique venant d'un contexte de programmation impératif.