====== Npda interpreter ======
{{tag>NPDA automata interpreter}}
===== Description =====
An interpreter for a nondeterministic pushdown automaton (NPDA)


**Source**:  The Art of Prolog
===== Download =====
Program source code: {{npda_interpreter.pl}}

===== Listing =====
<code prolog>
/*

	accept(Xs) :-

		The string represented by the list Xs is accepted by

		the NPDA defined by initial/1, delta/5, and final/1.

*/



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



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

	accept([],Q,[]) :- final(Q).





	initial(q0).			final(q1).



	delta(q0,X,S,q0,[X|S]).

	delta(q0,X,S,q1,[X|S]).

	delta(q0,_,S,q1,S).

	delta(q1,X,[X|S],q1,S).



%  Program 17.3: An interpreter for a nondeterministic pushdown automaton (NPDA)

%	Program 17.4:An NPDA for palindromes over a fi

ite alphabet

</code>
===== Comments =====