damn you prolog, I mean damn you university

Everybody should learn prolog. It's such a wonderful piece of idea.

If you express a graph as:

transition(S, a, T)
transition(S, b, U)
transition(T, 0, V)
transition(U, 0, K)
transition(T, c, K)
transition(U, a, U)
...

mark a special node as an accepting state

accept(c, K)

then validating input is only:

validate(S, [I|IS]) :-
  accept(I,S).
validate(S, [I|IS]) :-
  transition(S,I,X),
  validate(X,IS).

how daming is that.