You must review your past choices and try to find other choices that
will lead to the final state. This is called ** backtracking**.

With a *deterministic* automaton,
if you get stuck, you know that the string
is not accepted.
No choices were made in processing the string, so there are
no alternate paths to explore.
With a non-deterministic automaton,
if you get struck you must
review every choice you made to determine if
a different choice might lead to a final state.

It is easy for humans to back up when they are stuck,
but this is difficult to do in a computer program.
Automata are often used to design programs.
A good design requires a
** deterministic**
automaton.
If an automaton is deterministic,
then for each state there is one or zero transitions
for each character.
If there is no transition out of the current state,
the automaton stops and the string
is immediately rejected.

Luckily, any non-deterministic finite-state automaton can be redesigned as a deterministic finite-state automaton. There is an algorithm that does this, but usually it is easier to fuss around until you get the right design. Here is a deterministic version of the previous non-deterministic automaton that accepts Java integer literals:

Which of the following strings are accepted by the automaton?

String | 0 | 0x | -0xf | 0f | 0934 | +0xFABEL | 00X32 |
---|---|---|---|---|---|---|---|

Accept or Reject? |