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

I don't see the prolog part of this question. The answer highly depends on how you implemented this grammar.

My best guess would be to reverse the order of the rules, to have the terminating rules applied first.

Answer 3

I wrote this as a way to help limit solutions even though there are infinite solutions. But I realized there would be a way to rearrange the rules to get shorter results first.

Because ad --> a, ad, d. is evaluated before ad --> bc. it tries to satisfy ad --> a, ad, a. before ad --> bc.. I would put ad --> bc. before ad --> a, ad, a.. The same goes for the bc --> b, b, bc, c, c. and bc --> []. rules

As arian pointed out have the terminating rules applied first, would ensure the shorter solutions are found first.

I also want to point out that there are two solutions for [] s and s -> ad -> bc -> [] I would eliminate s --> []. as it's redundant.

All in all I would try this solution:

s --> ad.
a --> [a].
b --> [b].
c --> [c].
d --> [d].
ad --> bc.
bc --> [].
ad --> a, ad, d.
bc --> b, b, bc, c, c.

ORIGINAL POST:

I had to look up how to do counting (it's been a while since I did prolog) But there are an infinite number and since prolog tries to find all solutions it never stops looking, although I'm sure you'll hit a stack over flow or some error before then :).

One way to limit the number of results is to limit the size of the solution

 phrase(s, X), length(X, 4).

Gets all solutions with exactly 4 values, which would be

X = [a, a, d, d]
X = [b, b, c, c]

increasing to 6 would yield:

X = [a, a, a, d, d, d]
X = [a, b, b, c, c, d]

Or use ranges:

 phrase(s, X), length(X, Y), Y >= 4 , Y < 10, Y != 6.

Answer 4

@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.