Information Technology Reference
In-Depth Information
it is used to classify languages in terms of the time and space they need for recognition. For
example, it will be used to identify the class
NP
of languages that are recognized by nondeter-
ministic Turing machines in a number of steps that is polynomial in the length of their inputs.
(See Section
3.9.6
.) Many important combinatorial problems, such as the traveling salesperson
problem, fall into this class.
The formal definition of the NFSM is given in Section
4.1
, where the next-state function
δ
:
Q
2
Q
.Such
functions assign to each state
q
and input letter
a
a subset
δ
(
q
,
a
)
of the set
Q
of states of the
NFSM (2
Q
, the power set, is the set of all subsets of
Q
.ItisintroducedinSection
1.2.1
.)
Since the value of
δ
(
q
,
a
)
can be the empty set, there may be no successor to the state
q
on
input
a
.Also,since
δ
(
q
,
a
)
when viewed as a set can contain more than one element, a state
q
can have edges labeled
a
to several other states. Since a DFSM has a single successor to each
state on every input, a DFSM is an NFSM in which
δ
(
q
,
a
)
is a singleton set.
While a DFSM
M
accepts a string
w
if
w
causes
M
to move from the initial state to a
final state in
F
, an NFSM accepts
w
if there is some set of next-state choices for
w
that causes
M
to move from the initial state to a final state in
F
.
An NFSM can be viewed as a purely deterministic finite-state machine that has two inputs,
as suggested in Fig.
3.7
. The first, the
standard input
,
a
, accepts the user's data. The second,
the
choice input
,
c
, is used to choose a successor state when there is more than one. The in-
formation provided via the choice input is not under the control of the user supplying data via
the standard input. As a consequence, the machine is nondeterministic from the point of view
of the user but fully deterministic to an outside observer. It is assumed that the
choice agent
supplies the choice input and, with full knowledge of the input to be provided by the user,
chooses state transitions that, if possible, lead to acceptance of the user input. On the other
hand, the choice agent cannot force the machine to accept inputs for which it is not designed.
In an NFSM it is not required that a state
q
have a successor for each value of the standard
and choice inputs. This possibility is captured by allowing
δ
(
q
,
a
,
c
)
to have no value, denoted
by
δ
(
q
,
a
,
c
)=
×
Σ
→
Q
of the FSM is replaced by a next-state function
δ
:
Q
×
Σ
→
⊥
.
Figure
3.8
shows an NFSM that recognizes strings over
B
∗
that end in 00101. In this
figure parentheses surround the choice input when its value is needed to decide the next state.
In this machine the choice input is set to 1 when the choice agent knows that the user is about
to supply the suffix 00101.
Output
Standard Input
Choice Input
δ
λ
,
Memory
Figure 3.7
A nondeterministic finite-state machine modeled as a deterministic one that has a
second choice input whose value disambiguates the value of the next state.
Search WWH ::
Custom Search