Learn Prolog Now! DCG Practice Example
I have been progressing through Learn Prolog Now! as self-study and am now learning about Definite Clause Grammars. I am having some difficulty with one of the Practical Session's tasks. The task reads:
The formal language anb2mc2mdn consists of all strings of the following form: an unbroken block of as followed by an unbroken block of bs followed by an unbroken block of cs followed by an unbroken block of ds, such that the a and d blocks are exactly the same length, and the c and d blocks are also exactly the same length and furthermore consist of an even number of cs and ds respectively. For example, ε, abbccd, and aaabbbbccccddd all belong to anb2mc2mdn. Write a DCG that generates this language.
I am able to write rules that generate andn, b2mc2m, and even anb2m and c2mdn... but I can't seem to join all these rules into a开发者_开发知识库nb2mc2mdn. The following are my rules that can generate andn and b2mc2m.
s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].
s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].
Is anb2mc2mdn really a CFG, and is it possible to write a DCG using only what was taught in the lesson (no additional arguments or code, etc)? If so, can anyone offer me some guidance how I can join these so that I can solve the given task?
@Timothy, your answer works, but it generates duplicates:
?- 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
This can be fixed by removing one clause, leaving the DCG:
s --> x.
s --> a,s,d.
x --> [].
x --> b,b,x,c,c.
% a, b, c, d the same
This generates:
?- 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] ;
I believe I figured it out...
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
It's amusing to look at the solution and think, "I racked my brain over that?" But I guess that's half the fun of learning something new, especially when it's something like logic programing coming from an imperative programming background.
How about something like:
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)).
executing:
?- gen.
abbccd
abbbbccccd
abbbbbbccccccd
abbbbbbbbccccccccd
aabbccdd
aabbbbccccdd
aabbbbbbccccccdd
aabbbbbbbbccccccccdd
aaabbccddd
aaabbbbccccddd
aaabbbbbbccccccddd
aaabbbbbbbbccccccccddd
aaaabbccdddd
aaaabbbbccccdddd
aaaabbbbbbccccccdddd
aaaabbbbbbbbccccccccdddd
true.
精彩评论