Question - formal language in prolog

Question

I am trying to build a DCG which recognizes all lists which match this form : a^n b^2m c^2m d^n.
I have written up the following rules:
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

When I try to evaluate a string with those specifications, like the list [a,b,b,c,c,d], it works. But when I try to evaluate the query phrase(s, X) so that I can see all the possible strings returned by this grammar, it loops to infinity.

Is there something wrong with the way I have build the DCG?

Answer 1

You can enumerate the strings fairly with iterative deepening:

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

Answer 2

@Simon the approach of using DGCs is correct but there are two issues in your attempt.

The first one is that you have left recursion in clauses like the following:

ad --> a, ad, d.

And this is one of the reasons why it loops to infinity.

The second issue is that this formal language cannot be built as a context free grammar, therefore you need an extra variable such as count.

s(Count) --> a(Count),b(Count),c(Count),d(Count).
a(0) --> [].
a(succ(Count)) --> [a],a(Count).
b(0) --> [].
b(succ(Count)) --> [b,b],b(Count).
c(0) --> [].
c(succ(Count)) --> [c,c],c(Count).
d(0) --> [].
d(succ(Count)) --> [d],d(Count).

Then query it using the following goal s(_, L, []).

I know this is an old question but maybe someone finds the correct answer useful from now on.