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.