Reputation: 13
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?
Upvotes: 0
Views: 138
Reputation: 60034
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)))
Upvotes: 0
Reputation: 3059
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"
Upvotes: 1