Thus, no final state can be reached by processing w = 110, and hence the string
is not accepted.
Why Nondeterminism?
In reasoning about nondeterministic machines, we should be quite cautious in
using intuitive notions. Intuition can easily lead us astray, and we must be able to
give precise arguments to substantiate our conclusions. Nondeterminism is a
difficult concept. Digital computers are completely deterministic; their state at
any time is uniquely predictable from the input and the initial state. Thus it is
natural to ask why we study nondeterministic machines at all. We are trying to
model real systems, so why include such nonmechanical features as choice? We
can answer this question in various ways.
Many deterministic algorithms require that one make a choice at some stage.
A typical example is a game-playing program. Frequently, the best move is not
known, but can be found using an exhaustive search with backtracking. When
several alternatives are possible, we choose one and follow it until it becomes
clear whether or not it was best. If not, we retreat to the last decision point and
explore the other choices. A nondeterministic algorithm that can make the best
choice would be able to solve the problem without backtracking, but a
deterministic one can simulate nondeterminism with some extra work. For this
reason, nondeterministic machines can serve as models of search-and-backtrack
algorithms.
Nondeterminism is sometimes helpful in solving problems easily. Look at
the nfa in Figure 2.8. It is clear that there is a choice to be made. The first
alternative leads to the acceptance of the string a 3 , while the second accepts all
strings with an even number of a's. The language accepted by the nfa is {a 3 } ∪
{a 2 n : n ≥1}. While it is possible to find a dfa for this language, the
nondeterminism is quite natural. The language is the union of two quite different
sets, and the nondeterminism lets us decide at the outset which case we want.
The deterministic solution is not as obviously related to the definition, and so is
a little harder to find. As we go on, we will see other and more convincing
examples of the usefulness of nondeterminism.
is not accepted.
Why Nondeterminism?
In reasoning about nondeterministic machines, we should be quite cautious in
using intuitive notions. Intuition can easily lead us astray, and we must be able to
give precise arguments to substantiate our conclusions. Nondeterminism is a
difficult concept. Digital computers are completely deterministic; their state at
any time is uniquely predictable from the input and the initial state. Thus it is
natural to ask why we study nondeterministic machines at all. We are trying to
model real systems, so why include such nonmechanical features as choice? We
can answer this question in various ways.
Many deterministic algorithms require that one make a choice at some stage.
A typical example is a game-playing program. Frequently, the best move is not
known, but can be found using an exhaustive search with backtracking. When
several alternatives are possible, we choose one and follow it until it becomes
clear whether or not it was best. If not, we retreat to the last decision point and
explore the other choices. A nondeterministic algorithm that can make the best
choice would be able to solve the problem without backtracking, but a
deterministic one can simulate nondeterminism with some extra work. For this
reason, nondeterministic machines can serve as models of search-and-backtrack
algorithms.
Nondeterminism is sometimes helpful in solving problems easily. Look at
the nfa in Figure 2.8. It is clear that there is a choice to be made. The first
alternative leads to the acceptance of the string a 3 , while the second accepts all
strings with an even number of a's. The language accepted by the nfa is {a 3 } ∪
{a 2 n : n ≥1}. While it is possible to find a dfa for this language, the
nondeterminism is quite natural. The language is the union of two quite different
sets, and the nondeterminism lets us decide at the outset which case we want.
The deterministic solution is not as obviously related to the definition, and so is
a little harder to find. As we go on, we will see other and more convincing
examples of the usefulness of nondeterminism.