2.2.1 Using an FSA to Recognize Sheeptalk

After a while, with the parrot's help, the Doctor got to learn the language of the animals so well that he could talk to them himself and understand everything they said.

Hugh Lofting, The Story of Doctor Dolittle

Let's begin with the "sheep language" we discussed previously. Recall that we defined the sheep language as any string from the following (infinite) set:

baa!

baaaaa!

baaa!

baaaaaa!

baaaaaaa!

The regular expression for this kind of “sheeptalk” is /baa+!/. Fig. 2.10 shows an automaton for modeling this regular expression. The automaton (i.e., machine, also called finite automaton, finite-state automaton, or FSA) recognizes a set of strings, in this case the strings characterizing sheep talk, in the same way that a regular expression does. We represent the automaton as a directed graph: a finite set of vertices (also called nodes), together with a set of directed links between pairs of vertices called arcs. We’ll represent vertices with circles and arcs with arrows. The automaton has five states, which are represented by nodes in the graph. State 0 is the start state. In our examples state 0 will generally be the start state; to mark another state as the start state we can add an incoming arrow to the start state. State 4 is the final state or accepting state, which we represent by the double circle. It also has four transitions, which we represent by arcs in the graph.

The FSA can be used for recognizing (we also say accepting) strings in the following way. First, think of the input as being written on a long tape broken up into cells, with one symbol written in each cell of the tape, as in Fig. 2.11.

The machine starts in the start state $ (q_{0}) $, and iterates the following process: Check the next letter of the input. If it matches the symbol on an arc leaving the current state, then cross that arc, move to the next state, and also advance one symbol in the

input. If we are in the accepting state $ (q_4) $ when we run out of input, the machine has successfully recognized an instance of sheeptalk. If the machine never gets to the final state, either because it runs out of input, or it gets some input that doesn't match an arc (as in Fig. 2.11), or if it just happens to get stuck in some non-final state, we say the machine rejects or fails to accept an input.

We can also represent an automaton with a state-transition table. As in the graph notation, the state-transition table represents the start state, the accepting states, and what transitions leave each state with which symbols. Here's the state-transition table for the FSA of Figure 2.10.

We’ve marked state 4 with a colon to indicate that it’s a final state (you can have as many final states as you want), and the 0 indicates an illegal or missing transition. We can read the first row as “if we’re in state 0 and we see the input b we must go to state 1. If we’re in state 0 and we see the input a or !, we fail”.

More formally, a finite automaton is defined by the following five parameters:

$ Q = q_0 q_1 q_2 \ldots q_{N-1} $ a finite set of $ N $ states

$ \Sigma $ a finite input alphabet of symbols

$ q_{0} $ the start state

$ F $ the set of final states, $ F \subseteq Q $

the transition function or transition matrix between states. Given a state $ q \in Q $ and an input symbol $ i \in \Sigma $, $ \delta(q, i) $ returns a new state $ q' \in Q $. $ \delta $ is thus a relation from $ Q \times \Sigma $ to $ Q $;

For the sheeptalk automaton in Fig. 2.10, $ Q = \{q_0, q_1, q_2, q_3, q_4\} $, $ \Sigma = \{a, b, !\} $, $ F = \{q_4\} $, and $ \delta(q, i) $ is defined by the transition table in Fig. 2.12.

Figure 2.13 presents an algorithm for recognizing a string using a state-transition table. The algorithm is called D-RECOGNIZE for “deterministic recognizer”. A deterministic algorithm is one that has no choice points; the algorithm always knows what to do for any input. The next section will introduce non-deterministic automata that must make decisions about which states to move to.

D-RECOGNIZE takes as input a tape and an automaton. It returns accept if the string it is pointing to on the tape is accepted by the automaton, and reject otherwise. Note that since D-RECOGNIZE assumes it is already pointing at the string to be checked, its task is only a subpart of the general problem that we often use regular expressions for,

finding a string in a corpus. (The general problem is left as an exercise to the reader in Exercise 2.9.)

D-RECOGNIZE begins by setting the variable index to the beginning of the tape, and current-state to the machine's initial state. D-RECOGNIZE then enters a loop that drives the rest of the algorithm. It first checks whether it has reached the end of its input. If so, it either accepts the input (if the current state is an accept state) or rejects the input (if not).

If there is input left on the tape, D-RECOGNIZE looks at the transition table to decide which state to move to. The variable current-state indicates which row of the table to consult, while the current symbol on the tape indicates which column of the table to consult. The resulting transition-table cell is used to update the variable current-state and index is incremented to move forward on the tape. If the transition-table cell is empty then the machine has nowhere to go and must reject the input.

function D-RECOGNIZE(tape, machine) returns accept or reject

index←Beginning of tape

current-state←Initial state of machine

loop

if End of input has been reached then

if current-state is an accept state then

return accept

else

return reject

elsif transition-table[current-state, tape[index]] is empty then

return reject

else

current-state←transition-table[current-state, tape[index]]

index←index + 1

end

Figure 2.13 An algorithm for deterministic recognition of FSAs. This algorithm returns accept if the entire string it is pointing at is in the language defined by the FSA, and reject if the string is not in the language.

Figure 2.14 traces the execution of this algorithm on the sheep language FSA given the sample input string baaa!.

Before examining the beginning of the tape, the machine is in state $ q_0 $. Finding a $ b $ on input tape, it changes to state $ q_1 $ as indicated by the contents of transition-table $ [q_0,b] $ in Fig. 2.12 on page 13. It then finds an $ a $ and switches to state $ q_2 $, another $ a $ puts it in state $ q_3 $, a third $ a $ leaves it in state $ q_3 $, where it reads the “!”, and switches to state $ q_4 $. Since there is no more input, the End of input condition at the beginning of the loop is satisfied for the first time and the machine halts in $ q_4 $. State $ q_4 $ is an accepting state, and so the machine has accepted the string baaa! as a sentence in the sheep language.

The algorithm will fail whenever there is no legal transition for a given combination of state and input. The input $ abc $ will fail to be recognized since there is no legal transition out of state $ q_0 $ on the input a, (i.e., this entry of the transition table in Fig. 2.12 on page 13 has a 0). Even if the automaton had allowed an initial $ a $ it would have certainly failed on $ c $, since $ c $ isn't even in the sheeptalk alphabet! We can think of these “empty” elements in the table as if they all pointed at one “empty” state, which we might call the fail state or sink state. In a sense then, we could view any machine with empty transitions as if we had augmented it with a fail state, and drawn in all the extra arcs, so we always had somewhere to go from any state on any possible input. Just for completeness, Fig. 2.15 shows the FSA from Figure 2.10 with the fail state $ q_F $ filled in.