| << Prev | - Up - | Next >> |
Programs to work on top of FSA representations.
Now that we know how to represent FSAs, we would of course like to do something with them; we want to use them to generate and recognize strings. That is, we need programs to work on top of FSA representations. Those programs should be general enough, so that we don't have to know anything about the structure of a certain FSA before using it -- in particular, we would like these programs to be able to deal with deterministic as well as non-deterministic FSAs. Prolog helps us a lot with this point, because it's built-in backtracking mechanism provides us with the search tool that we need to deal with the non-determinism. Furthermore, Prolog is so declarative, that one and the same program can (up to a point) work as both a recognizer and a generator.
Let's first ignore the fact that there may be jump arcs and write a recognizer/generator for FSAs without jump arcs. We will define the predicate recognize/3 which takes the name of the automaton to be used as first argument, the number of the node you want to start from as second argument and a list of symbols representing the string that you want to recognize as third argument:
recognize(A,Node,SymbolList) :- ... For instance the query recognize(a1,1,[h,a,h,a,!]) should succeed, if the list of symbols [h,a,h,a,!] can be recognized by the FSA called a1 in Prolog's database starting from node 1 and ending in a final state.
We will define recognize/3 as a recursive predicate, which first tries to find a transition in the automaton A from state Node to some other state reading the first symbol of the list SymbolList and then calls itself with the node it can reach through this transition and the tail of SymbolList. The code for the predicate is found in recognize.pl .
In the base case, recognize/3 is called with an empty list, i.e. the whole input has been read. In this case, it succeeds if the Node is a final state in A:
recognize(A,Node,[]) :-
final(A,Node). In the case where SymbolList is not empty, we first retrieve a transition of A that starts from Node. Then we take this transition, thereby reading a symbol of the input, and recursively call recognize/3 again.
recognize(A,Node_1,String) :-
trans(A,Node_1,Node_2,Label),
traverse(Label,String,NewString),
recognize(A,Node_2,NewString).
The predicate traverse/3 checks that we can indeed take this transition, i.e. that the label of the transition is the same as the first symbol of the input list, and returns the input without the symbol that we have just read.
traverse(Label,[Label|Symbols],Symbols).Now, if Prolog should ever retrieve an arc from the database that later turns out to be a bad choice because it doesn't lead to success, it will (automatically) backtrack on the call to trans/4 in the second clause of recognize/3 and look for alternatives.
As promised, we can use recognize/3 in two different modes. In recognition mode, we want to give a list of symbols SymbolList and want to find out whether there is an initial node Node in A such that the query recognize(A,Node,SymbolList) returns yes. Here is a driver predicate for the recognition mode:
test(A,Symbols) :-
start(A,Node),
recognize(A,Node,Symbols). In generation mode, we want to get all lists of symbols which recognize/3 can generate using A and starting from its initial node. For this, we can just call test1/2 with an uninstantiated variable as second argument. test1/2 then selects an initial node and calls recognize/3 with this node as first argument and an uninstantiated second argument.
generate(A,X) :-
test(A,X).| << Prev | - Up - | Next >> |