Nondeterministic pushdown automaton interpreter adapted from Art of Prolog 2e, Ch 17

npda_palindrome.pl

accept(DCG, Xs) :-
    call(DCG, initial, Q),
    accept(DCG, Q, Xs, []).

accept(DCG, Q, [], []) :-
    call(DCG, final, Q).
accept(DCG, Q, [X|Xs], S) :-
    call(DCG, delta, Q, X, S, Q1, S1),
    accept(DCG, Q1, Xs, S1).

palindrome(initial, pushin).

palindrome(final, pushin). % empty palindrome
palindrome(final, poppin).

palindrome(delta, pushin, _, S,     poppin, S). % ignore middle character (odd-length palindrome)
palindrome(delta, pushin, X, S,     poppin, [X|S]). % push last character of first half (even-length palindrome)
palindrome(delta, pushin, X, S,     pushin, [X|S]). % keep pushin
palindrome(delta, poppin, X, [X|S], poppin, S). % pop

:- findnsols(6, Pal, accept(palindrome, Pal), Pals), maplist(writeln, Pals).