Re: Parsing Context-sensitive languages with Prolog

Markus Triska schrieb:
Alessandro <askmeformymail@xxxxxxxxxx> writes:

I seek a *good* exemple in Prolog, perhaps with the langage { a^n b^n
c^n } that is known to be context-sensitive

What about:

anbncn --> n_x(N, a), n_x(N, b), n_x(N, c).

n_x(0, _) --> [].
n_x(s(N), X) --> [X], n_x(N, X).

Yielding:

%?- anbncn(Ls, []).
%@ Ls = [] ;
%@ Ls = [a, b, c] ;
%@ Ls = [a, a, b, b, c, c] ;
%@ Ls = [a, a, a, b, b, b, c, c, c] a
%@ Yes

More attributive grammar, than context sensitive grammar
as intially defined by chomsky.

Context sensitive by chomsky, means production rules of
the form:

A1..An --> B1..Bm

i.e. the head is allowed to contain more than one literal.
Can't be translated directly to DCG, isn't it?

Bye

P.S.: Context sensitive grammar for a^n b^n c^n n>=1 would be:

s -->
s --> y a b c
y -->
y --> y a a x
a x a --> a a x
a x b --> a b b x
b x b --> b b x
b x c --> b c c

Best Regards
.