Writing a DCG containing same string reversed

210 views Asked by At

I am trying to write a dcg that accepts string of the form l0k, where l and k are strings over the alphabet {1, 2, 3} and l is k in reverse. What I have seems to work in that the first answer of a query is correct, but then it keeps going giving more and more wrong answers, and I am wondering if there is a way to fix this without using cuts. This is what I have at the moment:

s --> a(X), [0], a(X). 
s --> a(X), s, a(X). 
a(X) -->[X].
a --> [1].
a --> [2].
a --> [3].

For

 ?- s([1,2,3,3,2,1,0|L], []).
 

I am getting:

L = [1, 2, 3, 3, 2, 1]
    L = [0, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, 0, _1364, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, _1370, 0, _1370, _1364, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, _1370, _1376, 0, _1376, _1370, _1364, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, _1370, _1376, _1382, 0, _1382, _1376, _1370, _1364, 0, 1, 2, 3, 3, 2, 1] etc.
1

There are 1 answers

0
slago On BEST ANSWER

A possible solution:

s --> [0].
s --> a(X), s, a(X).

a(1) --> [1].
a(2) --> [2].
a(3) --> [3].

Examples:

?- phrase(s, [1,2,3,3,2,1,0|L], []).
L = [1, 2, 3, 3, 2, 1] ;
false.

?- length(L,_), phrase(s,L,[]).
L = [0] ;
L = [1, 0, 1] ;
L = [2, 0, 2] ;
L = [3, 0, 3] ;
L = [1, 1, 0, 1, 1] ;
L = [1, 2, 0, 2, 1] ;
L = [1, 3, 0, 3, 1] ;
L = [2, 1, 0, 1, 2] ;
L = [2, 2, 0, 2, 2] ;
L = [2, 3, 0, 3, 2] ;
L = [3, 1, 0, 1, 3] ;
L = [3, 2, 0, 2, 3] ;
L = [3, 3, 0, 3, 3] ;
L = [1, 1, 1, 0, 1, 1, 1] ;
L = [1, 1, 2, 0, 2, 1, 1] ;
L = [1, 1, 3, 0, 3, 1, 1] ;
L = [1, 2, 1, 0, 1, 2, 1] ;
L = [1, 2, 2, 0, 2, 2, 1] ;
L = [1, 2, 3, 0, 3, 2, 1] ;
...