Discrete Mathematics

294 DISCRETE

MATHEMATICS'--------------------------

The only nondeterminism is in the choice

of

start state. The machine guesses at the outset whether to

check for divisibility by 3

or

5. After that, the computation is deterministic.

Let

Q be the states

of

N.

We will build a deterministic machine M whose states are subsets

of

Q.

There

are 2

8

= 256

of

these in all, but most will be inaccessible (not reachable from the start state

of

M under any

input). Think about moving

pebbles-

for this particular automaton,

if

we start with pebbles on the start states

and move pebbles to mark all states the machine could possibly be in, we always have exactly ...