====== Ndfa interpreter ======
{{tag>NDFA automata interpreter}}
===== Description =====
An interpreter for a nondeterministic finite automaton (NDFA)

**Source**:  The Art of Prolog
===== Download =====
Program source code: {{ndfa_interpreter.pl}}
===== Listing =====
<code prolog>
/*
	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)*
</code>
===== Comments =====