We're gonna find how to express the ideas
behind finite automata more formally.
We'll see how to represent finite automata
either as graphs or tables, They are two
representations of the same idea. And
we're going to do a few proofs in
considerable detail and learn some useful
proof techniques, Especially, inductive
proofs. An alphabet is simply a finite set
of symbols. There are many examples. Two
standard alphabets we see frequently are
the ASCI and Unicode alphabets. An
alphabet we'll use frequently is the
binary alphabet consisting of only the
symbols zero and one. We'll also sometimes
use alphabets of letters like ABC. And in
the tennis example we use the alphabet of
outcomes consisting of the letters s and
o. Each protocol has a set of signals. And
the set of all signals used by a protocol
is also an alphabet. Strings are the usual
data type you've seen in languages like
[inaudible] or Java. That is, a string is
a sequence of symbols chosen from some
alphabet sigma. The strings over sigma are
those strings whose symbols are each
members of sigma. For example 011 Is the
string of over alphabet zero, one [sound],
[sound]. It is also a string over
alphabet, zero, one, and two. It just
happens not to have any twos. Unlike
programming languages, which typically put
quotes around strings, we're not going to
do that. And even though strings are lists
of symbols, we're not going to separate
the symbols by commas or other separators.
We'll just write down the strings like
this. We use the expression Sigma star for
the set of all strings over the alphabet
Sigma. The length of the string is the
number of positions in that string and a
special string is the empty string which
has length zero. You represent it by
epsilon. For example, the language zero
one star consists of all strings that
could be made from the symbols zero and
one. For example, epsilon, the empty
string, is in this language. There are two
strings of length one, the strings zero
and one. And there are four strings of
length two, and so on. Notice that we do
not make a distinction between a symbol
like zero and the string of length one
that consists of single instance of that
symbol, the string zero. We trust that the
context will make clear which we need.
Programming languages do make this
distinction, So in c for example we'd put
single quotes around the zero. If we meant
the symbol or character zero and we put
double quotes around it, if we Intended
the string, consisting of only the zero.
Languages are sets of strings and they can
be finite sets or infinite sets. The only
limitation we place on languages is that
there is some alphabet that is finite set
of symbols from which all the strings in
one language are composed. Here's an
example of a language L, were going to
meet several times. Its alphabet is 01 and
it contains all strings of zeros and ones
that do not have consecutive ones. So the
empty string is there, And both strings of
length one. Of the strings of length two,
all are there except one, one because that
obviously has two consecutive ones. Five
of the eight possible strings of length
three are there, as are eight of the
sixteen strings of length four. Here's a
little puzzle for you to think about. For
length zero through four we see there are
one, two, three, five, and eight strings.
Do you recognize the sequence, and can you
extend it to strings, five, six and so on?
And in particular, can you prove that your
prediction is correct? Now we'll give the
formal notation for deterministic finite
automata. There is a finite set of states,
and we usually use q as the set of states.
Don't ask me why it's q, it just is. And
there is a finite input alphabet. The
traditional name for the input alphabet is
sigma, again, for no known reason. There
is a transition function which we'll
discuss on the next slide. It is the guts
of the automaton since it tells us how the
automaton moves from state to state in
response to inputs. The traditional symbol
for the transition function is delta. One
of the states in q is the star state and
we designated q subzero typically. And
some of the states are designated final
states, or synonymously accepting states,
Final states are typically Denoted F. The
thing that makes the automaton work is the
transition function, This function,
usually denoted by delta, takes two
arguments, a state q, and an input symbol
a. It gives you back the state that the
automaton goes to when it is in state q,
and the next input symbol to arrive is a.
The function delta is total. That is, it
has a value for every state and symbol.
There are examples of automata where we
really don't want to continue in certain
situations. For example, our tennis
automaton did not have transitions out of
the [inaudible]. The states, where one
player or the other has won the game. To
fix up such situations we have to
introduce a dead state, A dead state is a
state that is not accepting. And it has a
transition to itself on every input
symbol. Once you get to a dead state, you
cannot leave it and you cannot ever
accept. So death is a pretty good
description of what is going on. We're
going to use the abbreviation DFA for
deterministic final automaton. The
deterministic means that there's unique
transition for every state and input
symbol. We are going to meet
non-deterministic automatons soon and
there, it's possible to transition too
many states from one state on one input.
Now, back to the matter of a dead state,
here's our tennis example. And you can
notice that the two accepting states do
not actually have any transitions out. So
we have a dead state and all the missing
transitions go to that state. The
transitions from the dead state are to
itself on all possible input symbols. Like
the tennis automaton, we can represent any
finite automaton by a graph. The nodes of
the graph are the states of the automaton.
The arcs of the transitions, there is an
arc from state or node p to state or node
q, labeled by all the input symbols a,
such that delta of p and a is q. For
example, This arch, would be present if
Delta of p and a and Delta of p and b were
both q. You represent the start state by
adding an arrow labeled start into that
state. And we indicate final states by
double circles. This is an interesting
example of an automaton that processes
text. The goal is to recognize that the
string read so far ends in ING. The start
state represents the condition where we
have made no progress towards seeing ING.
If in that state we next see I, we've made
some progress, so we go to the state that
says, I was the last symbol seen.
Otherwise we stay in the start state.
Because what we've seen so far is no help
in seeing ING. Now, from the saw I state.
If we next see an "n", then we have made
more progress. We go to: state saw "n". If
we see another "i", and state saw "i",
then we have not made progress, but
neither have we lost ground. We may be
bringing a word like "skiing", with a
double "i", thus the transition from state
saw "i" and "i" [inaudible] is to itself
and any symbol other than "i" and "n", we
go back from saw "i" to start state and
state: saw "in" If we next see a "G", then
we win. We have just seen ING as the last
three symbols. So we go to the accepting
state saw ING. On the other hand, if from
state saw IN, we next see an I, then the
pattern IN is broken, but a new pattern
beginning with I has started. So we go
into the, saw I state. On any input other
than IOG including n, we have no progress
at all, so go back to the start state.
Finally, from state saw ING, we can only
go state saw I if the next input is I, and
otherwise we must go to the start state.
Here's an automaton that represents the
simplest possible protocol for sending
data. The program is in one of two states,
Ready and Sending. It starts in the ready
state. Eventually it gets some signals
that some data has been loaded into its
buffer and at that point it enters the
sending state, where it does what is
necessary to transmit the content of the
buffer. The receiver will send back an ads
signal when the contents are received, in
which case we are ready to return to the
ready state. However if the receiver is
down, we may instead get a local timeout
signal that warns us something is wrong
and the buffer must be re-transmitted.
This automaton is not complete. There are
no final states because the automaton is
designed to run forever without rendering
a decision. Also, there are missing
transitions. It is okay to ignore act or
timeout signals if you're in the ready
state, staying in the ready state.
However, a data signal in the sending
state is an indication of an error, so we
might want to go to an error state. And
the error state is a dead state, so we
need transitions to itself on any of the
three inputs. A typical question that is
asked about protocols is whether you can
get to an error state. We could for
example make the error state the final.
And then ask if the language of the
automaton is empty. As we shall see there
is an algorithm to tell whether the
language of the [inaudible] of automaton
is empty, A question we could not ask. The
programs in general, in this example
however, it is easy really easy to see
that there is a path in the graph from the
start state to the final state so its
language is not empty and errors are
possible. For our running example were
going to use [inaudible], this language is
the set of binary strings that do not
contain two consecutive ones. State a is
where the [inaudible] would be whenever
the input string seems so far is good,
that is it contains no consecutive ones.
And also in state a, it is not ending on
one. Surely the state should be the start
state when no input is received. There are
no consecutive ones, and moreover, the
input so far does not end in a one. We get
to state b when the input is good, that
is, no two consecutive ones, but the last
symbol seen is a one. Notice the only way
to get to b is to be an a, and then to get
input one. C Is actually a dead state, You
are there whenever two consecutive ones
have been received. We arrive at c for the
first time from b. Which you recall, means
the previous input was one. And in state
b, we receive a second one. Once in state
c, we stay there, because once a string
has 1-1, you can never undo that fact, no
matter how many zeroes you see. We can
also represent automata by tables. Here's
our example automaton for strings without
consecutive ones shown as a transition
graph in the corner. And we also see a
representation of the same automaton as a
table. The rows each correspond to one of
the states. And the columns correspond to
the input samples. We indicate the final
stage by putting a star next to their
name. And the start take Is indicated by
an arrow. The entries of the table are the
values of the transition function applied
to the state that is the row and the
symbol that is the column. For example
this entry Is c because it is in the row
for the state b. And the column for input
symbol one. And we know that delta of b
and one is c. There are two important
conventions we're going to use. They let
us know the types of things without
declaring types. In particular, we can
distinguish between strings and
characters. We use lower case letters at
the end of the alphabet, w, x, y, and Z,
And sometimes U or V to represent strings.
When you see one of these letters, you
need to think, aha, that's a string. And
lower case letters near the beginning of
the alphabet will represent single
symbols. Again, we'll try to remind you at
first. But you have to think single symbol
when you see one of these letters. The
extended transition function delta is a
function that takes a state q and a string
w of any length, including zero. And tells
us where the automaton gets to. It follows
a path in the transition diagram, from q,
where the arcs are labeled by each of the
symbols of w in order. That is, we look
for the unique path from q, whose label's
forms w. In some material, you will see a
hat over the delta to remind you that it
is the standard version. However, as we
shall see, the standard delta agrees with
the given delta when the string w is of
length one, that is, it is a single
symbol. Thus, there is not really a need
to distinguish the standard and original
deltas. The definition of the extended
transition function delta is an induction
on the length of the string to which this
function is applied. For the basis, delta
of q and epsilon is q. That is, if you are
in state q and no input symbols arrive,
then you stay in state q. For the
induction, suppose the input string is WA.
By our convention, w is a string of some
length, possibly zero, and a is a single
symbol. The inductive rules says, that we
first see where you get to from state q,
on string of inputs w. That would be Delta
of QW. And then you see where you get from
that state, Whatever it is on the last
input a. In this example 001 is split into
w into 01 and a which is one. Then, we
have to compute delta of b and 01, and see
where it goes to on input one. Now, 01 is
broken into a string w that is just the
star, zero, and then a, which is one. So
we need to compute delta of b, zero, and
then see where we get to on input 1.'Kay,
But delta of b and zero is a. See, right
here, Thus, And we can replace delta of
being zero by the a, And now we have to
say what is the value of delta of a and
one. Well, that's b. Okay, So that's a b,
And we replace that b there. And then
finally delta, b, and one that's c. So,
that's our answer. Delta of b and zero
one, one is the state c. As I mentioned,
the extended delta sometimes is given a
hat. However we really don't need to
distinguish the two deltas because they
agree on single symbols, that is, if we
want the extended delta for a state q in a
string consisting of one symbol a,
formerly we treat that string as the empty
string followed by the symbol a. Then we
have to compute delta hat of q and epsilon
but we know about the basis rule that this
is q itself. Now if delta hat q and a is a
same state as delta of q and a. In fact, I
really cheated on the previous slide. I
needed delta hat of b and zero and just
went to the table and looked it up as if
it were delta of b and zero. Now we see
they are in fact the same so it was no
harm, no foul. There are many different
kinds of automaton. We have seen only a
bit of deterministic final automatons so
far but there are many others. But no
matter what kind of automaton its job is
to, is to define some language. We'll use
L of a to denote the language defined by
automaton a, For a deterministic find in
automaton. The language it defines is the
set of strings that may take the start
state to a final state. Formally, the
language of a DFA is the set of strings w.
Such that, the extended delta applied to
the start state, and this w, is a final
state. For example, consider our running
example of the automaton that accepts
strings without consecutive ones. And
consider the input, one zero one. It
should accept the string because it
obviously does not have consecutive ones.
The start state is a. And if we follow the
path labeled 101, we first go to b. Then
from b we follow the arch with a zero that
leads us back to a. The theory put in
another one so that gets us back to b
again. Since the path from a labeled one
zero one gets us to the final state, one
zero one is indeed accepted by the
automaton. Now this expression is called
the set former. It describes sets, in
particular while use it to describe
languages. In this example, it's
describing the languages of the automaton
that have served as our running example.
The second formula starts with a curly
brace. And then an expression of the
things we want to put in the set. In this
case the expression simply says that the
set consists of some strings w. We know
they are strings because of our
convention. The vertical bar can be read
such that. And then there follows a
description of what must be true for
something to be a member of the set. In
our example we say that the string
consists of zeros and ones and does not
have two consecutive ones. Many important
facts about automators that we might want
to prove are of the form that two sets,
typically languages of set of strings, are
really the same. We are going to prove
that the DFA we've been playing with
accepts the language I claim it does. The
set of binary strings without consecutive
1's, So one set is the language of the DFA
from our example. And the second set is
the language consisting of all strings of
zeros and ones without two consecutive
ones. I'm going to spend a good deal of
time proving this simple result because it
will give you all the details of how one
proves things about languages. In the
future I'm not going to be so focused on
proofs, but I think it is important that
everyone go through one of these proofs
and all its gory detail. To prove two
sets, s and t are equal, we generally need
to prove two things. That each is
contained in the other. That is we start
by assuming w is a member of one, say s.
And we use that fact to prove w is in the
other t. Then, we start over and we assume
w as in t, and we use that to prove w is
also in s. In what follows, we take s to
be the language of the DFA we have been
playing with, and t to be the set of
binary strings without consecutive ones.
First, we're going to prove that if w is
accepted by this automaton, the one shown
in the slide. Then w has no one, one's.
Okay, and the proof is in the induction on
the link of w. It turns out that if we
simply try to prove the statement on the
slide we fail. And I'll point out in a few
slides what goes wrong. A common trick for
inductive proofs is to make a more
detailed statement here than you really
want, because it makes the inductive proof
work. Here, we need to distinguish whether
an accepted string gets you to state a or
state b. Because we need to know whether
or not the string ends in one, Even though
at the conclusion, no 1-1s is true in both
states a and b. The inductive hypothesis
will be in two parts. Part one says that
if w gets you to state a, then not only is
w good, in the sense that it doesn't have
consecutive ones. Part two says that if w
gets you to state b, then w is still good,
but it must end in one. Remember, the
induction is on the length of w, so the
basis case is when w is the empty string,
the only string of length zero. We're
going to use bars around a string to
denote its length. And now, let's prove
part one of the basis. Delta of a in the
empty string is indeed equal to a. But the
conclusion is true since the empty string
does not have consecutive ones. For item
two things are a little trickier. It is
false that delta of a and the empty string
is b. But it's also false that the empty
string ends in one. However an important
principal of logic is that the statement
false implies false is true. That is
whenever the if portion of the statement
is false it doesn't matter what whether
the then portion is true or not, the
statement as a whole is true. Thus a
statement like, "If I am superman, then I
wear red undershorts." is a true statement
simply because I am not superman. You
don't have to concern yourself with the
color of my undershorts. The mathematical
term for an if then statement that is true
because the if part is false is that the
statement holds vacuously. Now let's
address the inductor step. We assume that
w is a string of [inaudible] at least one.
And we assume that the inductive
hypothesis the statements one and two from
the previous slide. About strings that get
the automaton to states a or b, is true
for strings shorter than w. Let's let w be
xa, where by our convention a is the last
symbol of w, and x is all the symbols,
possibly none, up to but not including the
last symbol of w. Since x is shorter than
w, we assume the inductive hypothesis for
x. We're going to prove both statements,
one and two, for w. Which, remember, we
broke up as a shorter string x followed by
the last symbol a. Let's start with
condition one, that is if delta of a and w
equals a then w is good. It has no
consecutive ones, and it does not end in
one. How can you get to a by reading
string x followed by symbol A? Well, look
at the diagram. The only transitions into
a are on input zero. That's this and that.
So symbol a must be zero. And immediately
that's a [inaudible] that w does not end
in one. Furthermore these transitions to a
are only from a and b. Thus x must get to
a or b. Now regardless of whether x gets
to a or b, we can conclude, using the
inductive hypothesis, that x is good. It
has no consecutive ones. This w which is x
followed by zero also has no consecutive
ones and it surely does not end in one.
Now for part two, If delta of a and w
equals b, then w is good and ends in one.
There's only one way to get to b. You have
to be in state a, and the input has to be
one. Thus, if w equals x, followed by a,
then x gets us to state a, and the symbol
a is a one. We can therefore conclude that
w ends in one. Apply the inductive
hypothesis to x and we conclude that x not
only has no consecutive ones, but doesn't
end in one. Any occurrence of one, one,
and w would either have to be at the end
or lie completely within x. We know it
doesn't lie within x, by the inductive
hypothesis. We know one, one cannot be at
the end, because x does not end in one.
And a is only a single one. We can clue
that the w's does not have consecutive
ones. Notice that if we don't use this
more complicated inductive hypothesis
where we distinguish between a and b
according to whether the string, x ends in
one that we cannot make the inductive
proof. If we know only that x gets us to a
or b then we might think that x gets us to
state a it ends at one, in which case w,
which would be XA, would have two
consecutive 1s. But we're not done, we
still have to prove that t is contained in
s, that is, if s is a good string with no
consecutive 1s that it is accepted by the
automaton. It is helpful the restate what
we need to prove in its contra-positive
form, which is logically equivalent to the
original. The contra positive of an if
then statement, say if x then y, is if not
y, then not x. We can see why this is an
equivalent statement, since if y is false,
it couldn't be that x is true. Because
whenever x is true, y is true. In this
case, x is the statement that w is a good
string with no one, ones. And y is the
statement that w is accepted by the
automaton. The contra positive is that w
is not accepted by the automaton, and w is
not a good string, that is, it contains
eleven as a substring. A deterministic
automaton has exactly one transition from
each state on each input symbol. Thus any
string w gets the automaton from the start
state to exactly one state. So the only
way w could not be accepted is if it gets
this automaton to state c. Notice that the
only way to get the automaton to c is for
some string x to get it to b and then for
an input one to follow. Once in c you stay
in c, so anything can follow the x and
one, We'll call that y. That is Any string
w that gets the automaton to state must
[inaudible] the form x1y where x gets to
be. We already observed that the only way
to get to b is by a string that ends in
one, since the only transition into b is
on one. Thus, x must be the form Z1 for
sum z. Thus, w, is really, z, one, one, y,
and, we can conclude that, if delta of a
and, w, is c, then, w, is bad. That is, it
contains two consecutive ones. Now, we
introduce a class of languages, called the
regular languages. These are the languages
that have a deterministic [inaudible]
accepting them. That means that the
language is, is exactly the set of strings
accepted by this automata. Soon we shall
see that there are several other ways to
describe the regular languages including
by regular expressions and
non-deterministic automata. While many
common languages are regular, there are
also many that are not. Intuitively,
finite automata cannot count beyond a
fixed number. Thus they cannot do things
like check whether they have seen the same
number of zeros as ones on their input. Or
check that parentheses are balanced in an
arithmetic expression. For those tasks we
need more powerful mechanisms such as
context-free grammars, which we will meet
soon enough. Here is an example of a
language that is simple to understand, but
is not a regular language. To understand
what this notation is saying we first need
to know that and exponent I on a symbol is
shorthand for the string consisting of I
copies of that symbol. Thus the zero to
the fourth means the string 0000. Thus, we
read this set [inaudible] as zero to the
n, one to the n, such that n is equal to
or greater than one, or more [inaudible].
The set of strings consisting of n zeroes
followed by n ones for sum n equal to or
greater than one. The strings of the
language l1 are thus 01, 0011, and so on.
Here's another example of a non regular
language, The set of strings that are
balance parentheses. The strings of
balanced parenthesis are those that can
appear in an arithmetic expression for
example the string zero of left paren,
right paren can appear in an expression
like (a+b)c. Or this string, can appear in
an expression like (a+b)(c+d). Examples of
strings that are not balanced are the
right paren followed by a left paren. This
is not balanced because no prefix of a
balanced string can have more left parens
than right parens. Obviously there is no
arithmetic expression that has this
sequence of parentheses as its sole set of
parentheses. Also, three lefts followed by
two rights. It's not balanced, because it
has more left per ends than right.
However, Regular languages are common. For
example in each language there is a format
for floating point numbers. And this
format can be quite complicated with
optional E's or decimal points and strings
of digits, that could be empty. But in all
programming languages I know about, the
set of strings that represent some
floating-point number is a regular
language. This is a very interesting case
illustrating what finite memory means. We
want to know if a binary number is
divisible by 23. We're going to read the
bits high order first. But if we have only
finite memory, how can we remember exactly
what sequence of bits has been read, since
the sequence can grow very long? But there
is a trick. We don't really need to
remember everything about the pitch red.
It is sufficient to remember what the
remainder is when divided by 23. Thus
we'll have 23 states, zero through 22.
These correspond to the 23 possible
remainders when an integer is divided by
23. The start state is zero because we
interpret the empty string as representing
the number zero. That may be a bit of an
assumption but nothing else makes sense
and treating it as zero makes everything
work out right. State zero is also the
only final state since we want inputs that
leave a remainder of zero when divided by
23. We're going to assume that the things
are working right after reading a binary
string value. That is w takes state zero
to the state that is the correct remainder
when w was divided by 23. I'm using the
C-style percent operator to denote the
remainder. You can read the percent as
modulo or mod, which is just another way
of saying the remainder when divided by.
The transition from each state I on input
zero, is to the state that is the
remainder of 2i/23. To see why this works,
we know that i=23a+b, for some integer a
and for some integer b in the range zero
to 22. That is, b equals i mod 23. Then 2i
is 45a+2b, since 46 is divisible by 23, 2i
by 23 is just 2b by 23. That is, when we
divide by 23 we can just get rid of the
46a. We know it will leave you a remainder
of zero. Thus, we can take the state b,
which is the remainder. Double it,
subtract 23 if it is 23 or more. And that
gives us the new remainder, and therefore,
the new state. We never need to know what
a is, and we never need to know I exactly.
For the same reason, when one arrives at
the input, we can go from state I to the
state that is the remainder of 2I+1 when
divided by 23. For example, twice fifteen
is 30. So from state fifteen we go to the
state that is the remainder of 30/23 or
state seven when the input is zero. From
state eleven on input one, we go to the
state that is the remainder of twice
(eleven+1)/23, that's state zero. So
whenever a string gets you to stay at
eleven, that is, the string leaves a
remainder of eleven when divided by 23.
That string, followed by a one, must be
divisible by 23, and therefore, must be
accepted. Interestingly in other regular
languages is a set of all binary strings
that if we read the strings in backwards
that is low [inaudible] byte first the
former binary entity that is divisible by
23. And there is nothing special about 23,
it could be any number in both this
example and the previous one. So for
example 0110100 is in this language
because when we reverse it we get 00101110
which has the value 46 in decimal and 46
is of course divisible by 23. It is really
tricky to design a DFA to accept this
reverse language. However there is a
theorem, which we shall see soon. It says
a language is, if a language is regular
then its reversal were to get to reversing
each of its strings is also a regular
language. The proof of this theorem will
let us construct the DFA for the reverse
language from the DFA we just saw.