 |
www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com |
|
|
|
Handling infinity
So far we have been rather textbookish in our examples. But a purely
textbookish finite automaton is something like distilled water---to
pure to be tasty. So we want to generalize the concept a bit. In
particular, we want to somewhat "relax" the finiteness constraint. But
first a minor point.
A minor point
In our examples so far the output set essentially consisted of some
symbols to be printed on the screen. To print the output on the
screen you need to call some function like printf(). Now, if you can
call printf() why not some other function? So here is the minor
point: The output set can very well be (and most often is) a set of
functions. Thus output 1 will mean "call function 1" and so on.
Allowing "infinity"
Why is it that we are always insisting on the finiteness of a
finite automaton? The reason is that we want to implement them using a
computer, and a computer can only handle finiteness. So in the strict
sense of the term, a computer-implemented DFA can never allow
infinity. But let's consider the following example.
An example
We want to implement the following automaton:
Input set : {UP,DOWN}
Output set : {all the integers, positive, negative, and zero}
State set : {all the integers, positive, negative, and zero}
Output function : if current input is i, and current state is s,
then output is
s.
Thus,
f(i,s)=s
State function :
If last state is s then next state
is
g(UP,s)=s+1
g(DOWN,s) = s-1
Initial state is 0.
Surely this is not a DFA, since the state set and the output set
are both infinite! But take a second look at the above
specification. Isn't the automaton something very well known to us?
Yes, it is just a counter that prints the count at each step, and the
input tells it whether to count up or down. So without going into any
fuss about DFA and finiteness, we can simply write the code for this
automaton as shown below.
void automaton(int input) {
static int state = 0;
printf("output = %d\n",state);
if(input == UP)
state = state + 1;
else /* input == DOWN */
state = state - 1;
}
So somehow we have implemented our "inifinite automaton" using a
computer!!! Well, not quite! The catch is that it will work fine only
while state is within the allowable integer range for
the computer used. After that we will have an overflow or
underflow. Assuming that your computer can represent integers from
-231 to 231-1, you have actually constructed a
DFA with a state set and output set both of size 232. This
is a huge size, and is as good as inifinity for most practical
purposes. Now, this is the big lesson to be learned. If the state
function or the output function can be implemented "nicely" as a
computer routine (as opposed to table look up) then we can often
ignore the finiteness restriction. In other words, the "finiteness" in
a DFA is to be construed as
it should be possible (read "easy") to write the code to implement
the state and output functions.
What is "easy"?
This is not hard to figure out. If the functions cannot be expressed as
math formulas (eg, the robot example, C comments example) then we have
to use a switch statement as shown earlier. Surely a
switch ceases to be nice if you have a list of 1000
cases dangling under it. In this case you can try the
table look up method. This ceases to be nice if the number of
states is like 231. However, a DFA with this many
states can be nicely handled if there are simple math formulas as
in the above example. And in these cases, you can handle such
big state sets, that for all intents and purposes it is just like
an infinite set.
|
