Learn Prolog Now! DCG Practice Example

Question

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 aⁿb^2mc^2mdⁿ 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 aⁿb^2mc^2mdⁿ. Write a DCG that generates this language.

I am able to write rules that generate aⁿdⁿ, b^2mc^2m, and even aⁿb^2m and c^2mdⁿ... but I can't seem to join all these rules into aⁿb^2mc^2mdⁿ. The following are my rules that can generate aⁿdⁿ and b^2mc^2m.

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

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

Is aⁿb^2mc^2mdⁿ 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?

Answer 1

@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] ;

Answer 2

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.

Answer 3

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.