The various interpretations of FSTNs as FSAs all involve FSAs that go from
state to state in a way that echoes a traversal of the network.
We thus turn now to the question of how to set about getting a computer to
traverse networks of the kind we have been examining. One way to imagine
the traversal of a network is to think of a kangaroo
that jumps from node
to node but which is constrained to take jumps only where there are arcs.
As the kangaroo
jumps about, portions of the input string are consumed, if the network
is being used for recognition, or portions of the output string are produced,
if the network is being used for generation. During recognition, we can
think of the input string being displayed in large letters on the wall, with
some kind of pointing device indicating which symbols remain to be
processed.
In a finite-state network, the kangaroo
is only allowed to make a jump if:
(1) The arc is labelled by a symbol which
is the same as the next symbol in the
input.
(2) The arc is labelled by an abbreviation and the next
symbol in
the input is one of the symbols covered by that abbreviation.
(3) The
arc is labelled '#'.
In the first two cases, the kangaroo moves the input
pointer forward one word and makes the jump. In the latter, it
simply jumps
across without changing the input pointer.
The kangaroo model is a useful way to think about the information that needs to be kept during the traversal of a network. If we wish to translate this into computer programs, we must think carefully about what the kangaroo needs to remember and what information is available to it. In doing recognition, our kangaroo needs to keep track of its own current location (which node it is at) and the pointer into the input string. Moreover, it is capable of moving that pointer. In summary, at any moment in the traversal of an FSTN, the state of the computation can be characterized by the following items:
R1. a node name (the kangaroo's location). R2. the remaining input string.
When the network is being used for generation, we will have to replace these items with the following:
P1. a node name (the kangaroo's location). P2. the output string generated so far.
Note that both R1 and R2 influence the future behaviour of the automaton in recognition mode, whereas P2 is irrelevant to future behaviour in generation mode.
Apart from our reference to the distinction between deterministic and non-deterministic FSTNs, we have not really addressed the issue of making choices in this discussion so far. In general, successful traversal of an FSTN involves choice and hence search. Given that R1, R2 characterize the complete current state of the traversal, this is precisely the information that we will need to keep if we wish to record different possibilities that need to be investigated. Following standard terminology, we shall call a collection of items R1, R2 that characterizes a complete (intermediate) state of a traversal a state, even though this word is also used to refer to a state of an FSA. (Woods uses the term configuration for a complete intermediate state of a parser, and this might be a more appropriate term to use here.) We will show a state as a sequence of two items, as follows:
<2, a h a !> ^ ^ | | | R2. remaining input (symbols to be processed) | R1. current node
This state represents the intermediate point of a traversal where the kangaroo has got to node 2 and still has to deal with the symbols 'a', 'h', 'a' and '!' (in that order).
When we are traversing a network, we need to keep track of both the current state, which expresses where we are now, and alternative states, which express other possibilities that could be tried as well as the current one. Consider what happens, for instance, if we are using the network of Figure 2.2 and get into the state just described.
In the network of Figure 2.2, there are two arcs leaving state 2: if the next symbol in the input is an 'a', then any of them could be traversed, leading to the following possible next states:
<1, h a !> <3, h a !>
In general, we might expect each of these to yield several next states, and each one of these to yield several next states, and so on, giving rise to a whole tree of possibilities, as shown in Figure 2.5.
In practice, the search tree arising from this example is not very complex, as most branches quickly lead to states from which no further progress can be made. Nevertheless, only one of the possible states can be investigated at a time - the current state. As the tree is generated, the new states need to be remembered somehow so that they can be investigated if necessary - they need to be added to some representation of the alternative states there are so far. One way of organizing the search is to keep a 'pool' of alternative states to be investigated. At each stage in the traversal, one of these alternatives is selected and made the current state. The valid next states from this state are worked out and added to the pool. Then another alternative is selected from the pool, and so on. We start off with a state in the set of alternatives for each initial node of the network. For instance, if s1 and s2 were the two initial nodes, s2 and s9 were the two final nodes, and the string was 'a b c d e', the initial set of alternative states would be:
<s1, a b c d e> <s2, a b c d e>
And the set of legitimate final states would be:
<s2, > <s9, >
If our machine winds up in either of these two states then it has succeeded in recognizing the string.
Here is an informal description of our algorithm:
(1) Create the set of alternative initial states (the initial pool).
(2) Do the following repeatedly:
(2.1) Select one of the alternative states (removing it from the pool).
(2.2) If it is a final state, stop and announce success.
Otherwise, (2.2.1) Calculate the valid next states that could follow from it. (2.2.2) Add these to the "pool" of alternatives.
(3) If the pool of alternatives ever becomes empty, stop and announce failure.
This is obviously not a complete description of what to do, because it does not specify how to decide which alternative to select at each stage. Two main approaches to this problem are depth-first and breadth-first search. In terms of the search tree, depth-first search follows a path deeper and deeper in the search tree and only moves up the tree to consider an alternative if all the possibilities below its current state have been tried. On the other hand, breadth-first search investigates states roughly in order of their depth in the tree. Intuitively, depth-first search involves preferring to investigate alternatives that have been added to the pool recently, whereas breadth-first search attempts to be fair by avoiding any alternative remaining too long in the pool before being investigated. We will see a lot more of these basic strategies later in this book.
Note also that this is a general search algorithm which can be used for any search task that can be characterized as an exploration of states of some kind.
How do we calculate the valid next states that follow from a given state <NODE, INPUT>? For each arc (with label L and destination D) leaving node NODE, we must include states in the set as follows:
(SYM) if L is a symbol and the first symbol of INPUT is the same, include <D, ... rest of INPUT ...> (ABB) if L is an abbreviation and the first symbol of INPUT is covered by the abbreviation, include <D, ... rest of INPUT ...> (JMP) if L is "#", include < D, INPUT >
Send us a comment.