Npda interpreter

Description

An interpreter for a nondeterministic pushdown automaton (NPDA)

Source: The Art of Prolog

Download

Program source code: npda_interpreter.pl

Listing

/*
 
	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

Comments

pl/prolog/pllib/npda_interpreter.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0