So that's pretty easy. Super-direct, much more than if you were using C or Java.
Let's write an interpreter for this graph that:
- Is given a list of named transitions ;
- Walks the transitions using the given graph along a path through that graph ;
- Accepts (Succeeds) the list if we end up at a final state ;
- Rejects (Fails) the list if we do not ;
- And.. let's say throws an exception if the list cannot be generated by the given graph.
Prolog gives us nondeterminism for free in case there are several paths. Which is nice.
We do not have an class to describe the automaton. In a sense, the Prolog program is the automaton. We just have a set of predicates which describe the automaton via inductive definitions. Actually, if you slap a module definition around the source below, you do have the object.
First describe the graph. This is just a set of Prolog facts.
As required, we give the transitions (labeled by atoms) between nodes (labeled by integers), plus we indicate which are the start and end nodes. There is no need to list the nodes or edges themselves.
delta(1,d,2). delta(2,a,2). delta(2,b,2). delta(2,d,4). delta(2,e,5). delta(2,c,3). delta(3,d,6). delta(6,c,5). start(1). end(4). end(5).
A simple database. This is just one possible representation of course.
And now for the graph walker. We could use Definite Clause Grammars here because we are handling a list, but lets' not.
First, a predicate which "accepts" or "rejects" a list of transitions.
It looks like:
% accepts(+Transitions)
It starts in a start state, then "walks" by removing transitions off the list until the list is empty. Then it checks whether it is at an end state.
accepts(Ts) :- % accept the list of transitions if... start(S), % you can accept the list starting accepts_from(S,Ts). % from a start state accepts_from(S,[T|Ts]) :- % accepts the transitions when at S if... delta(S,T,NextS), % there is a transition S->NextS via T accepts_from(NextS,Ts). % and you can accept the remaining Ts from NextS. (inductive definition) accepts_from(S,[]) :- % if there is no transition left, we accept if... end(S). % we are a final state
Ah, we wanted to throw if the path was impossible for that graph. So a little modification:
accepts(Ts) :- % accept the list of transitions if... start(S), % you can accept the list starting accepts_from(S,Ts). % from a start state accepts_from(S,[T|Ts]) :- % accepts the transitions when at S if... delta(S,T,NextS), % there is a transition S->NextS via T accepts_from(NextS,Ts). % and you can accept the remaining Ts from NextS. accepts_from(S,[T|Ts]) :- % accepts the transitions when at S if... \+ delta(S,T,NextS), % there is NO transition S->NextS via T format(string(Txt),"No transition at ~q to reach ~q",[S,[T|Ts]]), throw(Txt). accepts_from(S,[]) :- % if there is no transition left, we accept if... end(S). % we are a final state
And so:
?- accepts([d,a,b,a,b,b,b,c,d,c]). true ; % yup, accepts but maybe there are other paths? false. % nope ?- accepts([d,a,a,a,a,e]). true ; false. ?- accepts([d,a,a,a,a]). false. ?- accepts([d,c,e,a]). ERROR: Unhandled exception: "No transition at 3 to reach [e,a]"
The above code should also be able to find acceptable paths through the graph. But it does not:
?- accepts(T). ... infinite loop
This is not nice.
The primary reason for that is that accept/2 will immediately generate an infinite path looping at state 2 via transitions a and b. So one needs to add a "depth limiter" (the keyword is "iterative deepening").
The second reason would be that the test \+ delta(S,T,NextS) would succeed at node 4 for example (because there is nowhere to go from that node) and cause an exception before trying out the possibility of going nowhere (the last clause). So when generating, throwing is a hindrance, one just wants to reject.
Addendum: Also generate
The following only accepts/rejects and does not throw, but can also generate.
:- use_module(library(clpfd)). accepts(Ts,L) :- % Accept the list of transitions Ts of length L if start(S), % ...starting from a start state S accepts_from(S,Ts,L). % ...you can accept the Ts of length L. accepts_from(S,[T|Ts],L) :- % Accept the transitions [T|Ts] when at S if (nonvar(L) -> L >= 1 ; true), % L (if it is bound) is at least 1 (this can be replaced by L #> 0) delta(S,T,SN), % ...and there is a transition S->SN via T Lm #= L-1, % ...and the new length is **constrained to be** 1 less than the previous length accepts_from(SN,Ts,Lm). % ...and you can accept the remaining Ts of length Lm from SN. accepts_from(S,[],0) :- % If there is no transition left, length L must be 0 and we accept if end(S). % ...we are a final state. delta(1,d,2). delta(2,a,2). delta(2,b,2). delta(2,d,4). delta(2,e,5). delta(2,c,3). delta(3,d,6). delta(6,c,5). start(1). end(4). end(5). generate :- between(0,7,L), findall(Ts,accepts(Ts,L),Bag), length(Bag,BagLength), format("Found ~d paths of length ~d through the graph\n",[BagLength,L]), maplist({L}/[Ts]>>format("~d : ~q\n",[L,Ts]),Bag).
And so:
?- accepts([d,a,b,a,b,b,b,c,d,c],_). true ; false. ?- accepts([d,a,a,a,a],_). false. ?- accepts([d,c,e,a],_). false. ?- generate. Found 0 paths of length 0 through the graph true ; Found 0 paths of length 1 through the graph true ; Found 2 paths of length 2 through the graph 2 : [d,d] 2 : [d,e] true ; Found 4 paths of length 3 through the graph 3 : [d,a,d] 3 : [d,a,e] 3 : [d,b,d] 3 : [d,b,e] true ; Found 9 paths of length 4 through the graph 4 : [d,a,a,d] 4 : [d,a,a,e] 4 : [d,a,b,d] 4 : [d,a,b,e] 4 : [d,b,a,d] 4 : [d,b,a,e] 4 : [d,b,b,d] 4 : [d,b,b,e] 4 : [d,c,d,c] true
d, just usedin the head position of the list pattern. For example if you wanted to accept all lists that start withd, you'd just writeaccept[d|Tail]).and that's it. To add a condition for the tail it'd beaccept([d|Tail]) :- some_condition(Tail)., which would accept a list if and only if the list starts with a d and the tail of a list satisfiessome_condition.