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?
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"