Information Technology Reference
In-Depth Information
4.1 Finite-State Machine Models
The deterministic finite-state machine (DFSM), introduced in Section
3.1
, has a set of states,
including an initial state and one or more final states. At each unit of time a DFSM is given
a letter from its input alphabet. This causes the machine to move from its current state to a
potentially new state. While in a state, the DFSM produces a letter from its output alphabet.
Such a machine computes the function defined by the mapping from strings of input letters
to strings of output letters. DFSMs can also be used to accept strings. A string is accepted
by a DFSM if the last state entered by the machine on that input string is a final state. The
language recognized by a DFSM is the set of strings that it accepts.
Although there are languages that cannot be accepted by any machine with a finite number
of states, it is important to note that all realistic computational problems are finite in nature
and can be solved by FSMs. However, important opportunities to simplify computations may
be missed if we do not view them as requiring potentially infinite storage, such as that provided
by pushdown automata, machines that store data on a pushdown stack. (Pushdown automata
are formally introduced in Section
4.8
.)
The nondeterministic finite-state machine (NFSM) was also introduced in Section
3.1
.
The NFSM has the property that for a given state and input letter there may be several states
to which it could move. Also for some state and input letter there may be no possible move. We
say that an NFSM accepts a string if there is a sequence of next-state choices (see Section
3.1.5
)
that can be made, when necessary, so that the string causes the NFSM to enter a final state.
The language accepted by such a machine is the set of strings it accepts.
Although nondeterminism is a useful tool in describing languages and computations, non-
deterministic computations are very expensive to simulate deterministically: the deterministic
simulation time can grow as an exponential function of the nondeterministic computation
time. We explore nondeterminism here to gain experience with it. This will be useful in
Chapter
8
when we classify languages by the ability of nondeterministic machines of infinite
storage capacity to accept them. However, as we shall see, nondeterminism offers no ad-
vantage for finite-state machines in that both DFSMs and NFSMs recognize the same set of
languages.
We now begin our formal treatment of these machine models. Since this chapter is con-
cerned only with language recognition, we give an abbreviated definition of the deterministic
FSM that ignores the output function. We also give a formal definition of the nondeterministic
finite-state machine that agrees with that given in Section
3.1.5
. We recall that we interpreted
such a machine as a deterministic FSM that possesses a choice input through which a choice
agent specifies the state transition to take if more than one is possible.
DEFINITION
4.1.1
A deterministic
finite-state machine (DFSM)
M
is a five-tuple
M
=
(Σ
,
Q
,
δ
,
s
,
F
)
where
Σ
is the
input alphabet
,
Q
is the finite
set of states
,
δ
:
Q
Q
is
the
next-state function
,
s
is the
initial state
,and
F
is the
set of final states
.TheDFSM
M
accepts the input string
w
×
Σ
→
Σ
∗
if the last state entered by
M
on application of
w
starting in
state
s
is a member of the set
F
.
M
recognizes the language
L
(
M
)
consisting of all such strings.
A
nondeterministic FSM (NFSM)
is similarly defined except that the next-state function
δ
is replaced by a
next-set function
δ
:
Q
∈
2
Q
that
associates a set of states with each
state-input pair
(
q
,
a
)
.TheNFSM
M
accepts the string
w
×
Σ
→
Σ
∗
if there are next-state choices,
whenever more than one exists, such that the last state entered under the input string
w
is a member
of
F
.
M
accepts the language
L
(
M
)
consisting of all such strings.
∈
Search WWH ::
Custom Search