Ndfa interpreter

An interpreter for a nondeterministic finite automaton (NDFA)

Source: The Art of Prolog

Program source code: ndfa_interpreter.pl

/*
	accept(Xs) :-
		The string represented by the list Xs is accepted by
		the NDFA defined by initial/1, delta/3, and final/1.
*/
	accept(Xs) :- initial(Q), accept(Xs,Q).
 
	accept([X|Xs],Q) :- delta(Q,X,Q1), accept(Xs,Q1).
	accept([],Q) :- final(Q).
 
 
	initial(q0).
	final(q0).
 
	delta(q0,a,q1).
	delta(q1,b,q0).
 
%   Program 17.1: An interpreter for a nondeterministic finite automaton (NDFA)
%	Program 17.2: An NDFA that accepts the language (ab)*