Machines with Memory - Models of Computation: Exploring the Power of Computing - page 100

0 ( 0 ) ,1

0 ( 1 )

0 1 0 1

q 0 q 1 q 2 q 3 q 4 q 5

Start

Figure 3.8 A nondeterministic FSM that accepts binary strings ending in 00101. Choice
inputs are shown in parentheses for those user inputs for which the value of choice inputs can
disambiguate next-state moves.

0 ( 0 ) ,1 ( 0 )

0 ( 1 ) ,1 ( 1 )

q 0 q 5

Start

Figure 3.9 An example of an NFSM whose choice agent (its values are in parentheses) accepts
not only strings in a language L ,butallstrings.

Although we use the anthropomorphic phrase “choice agent,” it is important to note that
this choice agent cannot freely decide which strings to accept and which not. Instead, it must
when possible make choices leading to acceptance. Consider, for example, the machine in
Fig. 3.9 . It would appear that its choice agent can accept strings in an arbitrary language L .In
fact, the language that it accepts contains all strings.
Given a string w in the language L accepted by an NFSM, a choice string that leads to its
acceptance is said to be a succinct certificate for its membership in L .
It is important to note that the nondeterministic finite-state machine is not a model of
reality, but is used instead primarily to classify languages. In Section 4.1 we explore the
language-recognition capability of the deterministic and nondeterministic finite-state machines
and show that they are the same. However, the situation is not so clear with regard to Turing
machines that have access to unlimited storage capacity. In this case, we do not know whether
or not the set of languages accepted in polynomial time on deterministic Turing machines (the
class P ) is the same set of languages that is accepted in polynomial time by nondeterministic
Turing machines (the class NP ).

3.2 Simulating FSMs with Shallow Circuits*
In Section 3.1 we demonstrated that every T -step FSM computation can be simulated by
a circuit whose size and depth are both O ( T ) . In this section we show that every T -step
finite-state machine computation can be simulated by a circuit whose size and depth are O ( T )
and O (log T ) , respectively. While this seems a serious improvement in the depth bound, the
coefficients hidden in the big- O notation for both bounds depend on the number of states of
the FSM and can be very large. Nevertheless, for simple problems, such as binary addition, the