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?

Fugger

I think, if I understood your Question, it is because there are many trees that can be created, since there are loops in your Grammar – Wardship

And how should I correct this problem? :-? – Fugger

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.

Dorian

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.

Avirulent

Answer 3

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.

Reinold

The grammar is already specified as Prolog code, using DCG notation. If you reorder the ad//0 and bc//0 rules, it indeed terminates existentially (i.e., the most general query then yields solutions) but enumerates the strings unfairly: There are finite strings that are elements of the grammar, but never generated. See the iterative deepening query above for one way to solve this. – Dorian

Answer 4

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.

Octonary

Your queries do not yield the results you cite, try your own example "phrase(s, X), length(X, 4)" to see that it only finds a single solution. Increasing it to 6 yields no solution at all, and the last query is syntactically invalid. – Dorian