Nondeterministic finite automaton implementation in 2 lines of Prolog

gistfile1.pl

% Nondeterministic finite automaton implementation
%
% Author: Cesar L. B. Silveira <[email protected]>
%
% This is public domain code.
%
% Usage:
%
%   nfa(INPUT_STRING, DESCRIPTION, INITIAL_STATE, FINAL_STATES).
%
%   Where:
%
%     INPUT_STRING  - list of symbols e.g. [a, b, b, a, b]
%     DESCRIPTION   - automaton description as a list of 3-tuples in the format
%                     (state, symbol, next_state) e.g. [(q0, a, q1),
%                     (q0, b, q0), (q1, a, q1), (q1, b, q1)
%     INITIAL_STATE - symbol for initial state e.g. q0
%     FINAL_STATE   - list of final states e.g. [q1]
%
%   Prolog will answer "true" if the automaton recognizes the input string,
%   "false" otherwise.

nfa([], _, S, F) :- member(S, F).
nfa([A|X], D, S, F) :- member((S, A, T), D), nfa(X, D, T, F).