/* Prolog program for working with a Finite State Automaton
   S. Tanimoto, for CSE 341, June 2003.  */

arc(s0, 0, s0).
arc(s0, 1, s1).
arc(s1, 0, s2).
arc(s1, 1, s1).
arc(s2, 0, s0).
arc(s2, 1, s3).
arc(s3, 0, s2).
arc(s3, 1, s1).

start(s0).
final(s3).

acceptsFrom([], S) :- final(S).
acceptsFrom([H|T], S) :- arc(S, H, S2), acceptsFrom(T, S2).

accepts(Seq) :- start(S), acceptsFrom(Seq, S).

/* Sample queries:
    Test to see if a particular sequence is accepted:
       accepts([0, 1, 0, 1]).
    Ask what 5-element sequences are accepted by the FSA:
       accepts([A1, A2, A3, A4, A5]).
*/