Today we begin with an informal introduction to finite automata. I'll
officer some brief remarks about their uses, and then move to an extended example
of an automaton that describes how a game of tennis is scored. The finite automaton
is a mathematical model, but fortunately, it is a model that should be quite
familiar. You can think of it either as a graph or as a table. The finite automaton
is simple because it stores only a finite amount of information. That can be bad
because in many applications there is no limit on the amount of information we need
to remember about what has happened in the past. When that is the case, the finite
automaton is not a useful model. But the finiteness of memory is great when the
model can be used because we can do a number of things with finite automata that
we cannot do with programs in general. For example given a program, you cannot really
tell anything about it, what it does or whether there is a shorter program that
does the same thing. However, you can tell whether two automata do the same thing or
whether there is a smaller automata that does the same as a given automata. You
could also tell whether a automaton does anything at all. That ability lets us tell
for example whether there are input sequences that cause automaton to get to
an error state, Which in turn lets us check whether protocols or other simple
systems have flaws. A finite automaton is built around a finite collection of
states. Each state has a name and that name represents what is remembered about
its history. States change in response to inputs. Inputs are either characters, if
we are doing something like processing text, or events, if we are modeling
something like a communication protocol. The rules that give the new state for each
current state an input are called the transitions. The [inaudible] automaton is
useful in a number of computing applications. We mentioned the design and
verification of communication protocols in digital circuits, and together with the
related formalism called regular expressions they are important in text
searching algorithms. They are essential for the portion of a compiler that breaks
the input into tokens, identifiers, key words like if and so on. You find automata
in regular expressions and many other applications as well, typically where a
simple language is needed to describe patterns that are sequences of symbols or
events of some sort. To see the power and also the limitations of a finite automaton
we shall take up an example scoring a game of tennis. If you don't play tennis, it's
almost like ping pong except you're really tiny and you stand on the table. Depending
on which page comes first in response to the search query, you'll find it was
invented in the twelfth century or in 1879 by people who evidently had too much time
on their hands. The scoring system is arcane with matches consisting of sets
which consist of games. Games consist of points where one player or the other wins
by causing the other player to hit the ball off court or into the net. We'll talk
about scoring a game. One player is server throughout the game. To win the game you
must have at least four points. But you also must win by at least two points. The
states we are going to use for the scoring automaton represent the numbers of points
won by each player, and they have strange names, which we'll see as we go. The
inputs are events in which one player wins a point. S for the server wins and O for
the opponent wins. It is common to represent a finite automaton by a graph
with nodes for states and arrows labeled. [inaudible] by the input for transitions.
Here's the first state of the automaton that scores tennis games. The name of this
state is love. You may ask what's love got to do, got to do with it. But that's what
zero is called in tennis. The state love represents the history in which nothing
has happened. And we indicate that history begins with this state by an arrow labeled
start. The first point will be won by one of the two players. So there are two
transitions out of love, One labeled S, the other O. You might [inaudible] think
the names of the states would be 1-0, and 0-1, 'cause the server's score always goes
first, but they're not. In tennis, there is a fiction that you score fifteen for
winning a point. And zero isn't zero, it's love. The next point can lead to three
states. Two where one player has won both points, and one where they're tied at one
each. Here are the states with their names. There is something interesting
about the fifteen all state. It has forgotten how we got there. We know the
sequence of inputs was either SO, or OS, but we don't know which, Doesn't matter of
course, that's the good thing about finding Andromeda. They only remember what
must be remembered. In state fifteen all, the question of who won the first of the
two points can't have any effect on the outcome. After another point, there are
four new states the game could be in. They have the expected names, except people are
too lazy to say 45 so they just say 40. Now let's look at the transitions from the
state 40 love. The server is well ahead and can win on the next point. If the
server wins, we'll go to a state indicating that win. The game is over, and
the automaton has no further moves. We indicate this output of the automaton by
calling the state a final state. And we indicate it as final by a double circle.
There's another state reachable from the [inaudible] of 40, if the next input
indicates the opponent won the fourth point. There are three other new states as
well, called 40, fifteen, 30 all and 1540. Which indicates that four points have been
played, with 3,2, or one of these points won by the server. From 40-15 state the
server wins the point. We go to the server one state. But if the opponent wins the
point we go to a new state called 40-30. A similar thing happens in 15-40 and from 30
all we can go either to the 40-30 or the 30-40 state. Now, let's look at the state
30-40. If the server wins the next point, they've won the game but if the opponent
wins then the game is tied. The name for this state is deuce. The deuce state is
quite interesting, It Remembers that the game is tied, but it remembers neither the
sequence of wins and losses of points, nor even how many points have been played and
the 30,40 state it happens similarly. Next consider what happens in deice, you have
to win by two points or it is impossible for either player to win immediately. If
the server wins the next point, they are ahead by one point, although we don't know
how many points in total have been played. The strange thing for this state is add
in, or advantage in, in refers to the server. Symmetrically if the opponent wins
the in state deuce we go to a state add out, the out refers to the opponent. But
in state add in if the server wins the next point they win the game. But if the
opponent wins you're back to deuce. Likewise, from add out, a server win puts
you back in deuce, but an opponent win gives the opponent the game. We can now
look at the entire transition diagram for the finite automaton. While most of it
just allows flow away from the start state, the loops involving deuce add in
and add out, that is these, they allow for cycles and for an infinite number of
possible strings of S's and O's to lead to one of the final states. The job of an
automaton is to process strings of input symbols or input strings. We always begin.
The start state, and we read each input symbol in order. For each input symbol we
follow the transition from the state we are in to discover what the new state is.
We accept the string if we wind up in a final state after processing the entire
input. Here is an example. Here is our input string. It represents a game in
which the server and opponent alternate winning points until the very end When the
server wins two in a row. We'll mark the current state by the star, and initially
the current state is the star state, that's where [inaudible] find in a time of
the start out. The arrow indicates which input we are about to process. So, here we
are about to process the first event were the server wins the first point. We're
going to follow the transition of the state love, labeled S. Here we've made the
first transition. Next input is O and we're in state 15-love. The transition
form that state on O is the state fifteen all. In state fifteen all we see another S
on the input so we go to state 30 fifteen. An O takes us to state 30 all. Then on S
we go to state 40 30. From there we go on O to deuce And from deuce on S to add in
From there on O back to deuce. And another cycle on S and O between add in and deuce.
Now come the first of the two messes. This S takes us to add in again, but the second
S takes us to the server win state. Good going server. Now let's get a bit more
formal. The job of a finite automaton is to process strings of inputs and accept or
reject them. It accepts the string if it leads from the start state to a final
state. Accepting state is a pseudonym for final state. A language is simply a set of
strings and the formalism used for [inaudible]. The language accepted by an
automaton, A is denoted L of A. In our class example we called the two states
where one of the players wins the final state. In that case the language of the
[inaudible] is a set of strings of S's and O's that end the game no matter who wins.
We can change the final states, say by making only the server win state be final.
Then the automaton would have a different language. The set of strings of S's and
O's that lead to a automaton by the server. Or we can make only the opponent
wins be final and have the language of ways the opponent is going to win.