go to previous page   go to home page   go to next page


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

Converting Non-deterministic to Deterministic

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?

Accept or