Free of context grammar in prolog - example

Question

I'm studying free of context grammar using the functional language Prolog. I'm trying to solve this exercise, but I'm in trouble designing a grammar to recognize the language.

We know that the language {aˆn bˆn cˆn | n e N} cannot be recognized by a free of context grammar. Even so, it is possible to recognize this language in Prolog, via attributes. Write a Prolog grammar that recognizes this language.

Could someone help me to write this grammar in Prolog?

Answer 1

The implementation can be found here.

:- op(150, fx, #).

start(N) --> as(N), bs(N), cs(N).

as(0) --> [].
as(N0) --> { #N0 #> 0, #N #= #N0-1 }, [a], as(N).

bs(0) --> [].
bs(N0) --> { #N0 #> 0, #N #= #N0-1 }, [b], bs(N).

cs(0) --> [].
cs(N0) --> { #N0 #> 0, #N #= #N0-1 }, [c], cs(N).

Then the query:

?- phrase(start(N), Cs).
   N = 0, Cs = []
;  N = 1, Cs = "abc"
;  N = 2, Cs = "aabbcc"

Answer 2

By means of Peano arithmetic it's easy to implement the grammar in pure Prolog, for instance

an_bn_cn(N) --> count_seq(a,N), count_seq(b,N), count_seq(c,N).

count_seq(Terminal,s(N)) --> [Terminal], count_seq(Terminal,N).
count_seq(_,0) --> [].

Note that, strictly speaking, this would be more general than necessary, since the (synthetized) attribute N is computed on the generic production (count_seq//2), instead of the productions a,b,c. You may need to adapt the code to your requirements.

Testing in swi-prolog:

?- phrase(an_bn_cn(N),[a,a,b,b,c,c]).
N = s(s(0)) .

?- phrase(an_bn_cn(N),[a,a,b,b,c,c,c]).
false.

?- phrase(an_bn_cn(N),[a,a,b,b,c,c]).
N = s(s(0)) ;
false.

?- length(S,_),phrase(an_bn_cn(N),S).
S = [],
N = 0 ;
S = [a, b, c],
N = s(0) ;
S = [a, a, b, b, c, c],
N = s(s(0)) ;
S = [a, a, a, b, b, b, c, c, c],
N = s(s(s(0)))