Section 9.3 Finite-State Machines
737
A regular set may be described by more than one regular expression. For
example, the set of all strings of 0s and 1s, which we already know from Example
32(c) to be described by (0 ~ 1)*, is also described by the regular expression
3(0 ~ 1*)* ~ (01)* 4*. We might, therefore, write the equation
(0 ~ 1)* = 3(0 ~ 1*)* ~ (01)* 4*
Although we may be quite willing to accept this particular equation, it can be
difficult to decide in general whether two regular expressions are equal, that is,
whether they represent the same set. An efficient algorithm that will make this
decision for any two regular expressions has not been found.
We have introduced regular sets because, as it turns out, these are exactly the
sets finite-state machines are capable of recognizing. This result was first proved
by the American mathematician Stephen Kleene in 1956. We state his theorem
here without proof.
tHeoRem KLEEnE’s thEorEM
Any set recognized by a finite-state machine is regular, and any regular set can be
recognized by some finite-state machine.
Kleene’s theorem outlines the limitations as well as the capabilities of finite state
machines—there are certainly many sets that are not regular. For example, consider S = 50
n
1
n
0 n ≥ 06 where a
n
stands for a string of n copies of a. Strings in
S have some number of 0s followed by the same number of 1s. S is not regular.
(Notice that 0*1* does not do the job.) By Kleene’s theorem, there is no finitestate machine capable of recognizing S. Yet S seems like such a reasonable set,
and surely we humans could count a string of 0s followed by 1s and see whether
we had the same number of 1s as 0s. This lapse suggests some deficiency in our
use of a finite-state machine as a model of computation. We will investigate this
further in Section 9.4.
Machine Minimization
Although we have treated finite-state machines as abstractions, circuits that act like
finite-state machines can be built from electronic devices like the logic elements of
Section 8.2 and others. If we wish to construct a physical machine, the number of
internal states is a factor in the cost of construction. Minimization is the process
of finding, for a given finite-state machine M, a machine M′ with two properties:
1. If M and M′ are both begun in their respective start states and are given
the same sequence of input symbols, they will produce identical output
sequences.
2. M′ has, if possible, fewer states than M (if this is not possible, then M is
already a minimal machine and cannot be further reduced).
Unreachable States
First, let’s observe that we can remove any unreachable states of M, those states
that cannot be attained from the starting state no matter what input sequence
occurs.
737
A regular set may be described by more than one regular expression. For
example, the set of all strings of 0s and 1s, which we already know from Example
32(c) to be described by (0 ~ 1)*, is also described by the regular expression
3(0 ~ 1*)* ~ (01)* 4*. We might, therefore, write the equation
(0 ~ 1)* = 3(0 ~ 1*)* ~ (01)* 4*
Although we may be quite willing to accept this particular equation, it can be
difficult to decide in general whether two regular expressions are equal, that is,
whether they represent the same set. An efficient algorithm that will make this
decision for any two regular expressions has not been found.
We have introduced regular sets because, as it turns out, these are exactly the
sets finite-state machines are capable of recognizing. This result was first proved
by the American mathematician Stephen Kleene in 1956. We state his theorem
here without proof.
tHeoRem KLEEnE’s thEorEM
Any set recognized by a finite-state machine is regular, and any regular set can be
recognized by some finite-state machine.
Kleene’s theorem outlines the limitations as well as the capabilities of finite state
machines—there are certainly many sets that are not regular. For example, consider S = 50
n
1
n
0 n ≥ 06 where a
n
stands for a string of n copies of a. Strings in
S have some number of 0s followed by the same number of 1s. S is not regular.
(Notice that 0*1* does not do the job.) By Kleene’s theorem, there is no finitestate machine capable of recognizing S. Yet S seems like such a reasonable set,
and surely we humans could count a string of 0s followed by 1s and see whether
we had the same number of 1s as 0s. This lapse suggests some deficiency in our
use of a finite-state machine as a model of computation. We will investigate this
further in Section 9.4.
Machine Minimization
Although we have treated finite-state machines as abstractions, circuits that act like
finite-state machines can be built from electronic devices like the logic elements of
Section 8.2 and others. If we wish to construct a physical machine, the number of
internal states is a factor in the cost of construction. Minimization is the process
of finding, for a given finite-state machine M, a machine M′ with two properties:
1. If M and M′ are both begun in their respective start states and are given
the same sequence of input symbols, they will produce identical output
sequences.
2. M′ has, if possible, fewer states than M (if this is not possible, then M is
already a minimal machine and cannot be further reduced).
Unreachable States
First, let’s observe that we can remove any unreachable states of M, those states
that cannot be attained from the starting state no matter what input sequence
occurs.