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

Is the string "+0Xf" accepted?




Finite Automaton

In deciding if the string "+0Xf" is accepted you reach state q1 with 0 as the current character. There are two transitions you can take. Which one do you choose? If you make the wrong choice you end up stuck (in state q2 with X as the current character). If you make the other choice you do not get stuck.

If an automaton has a state with two or more transitions for a particular character, or any epsilon-transitions, it is a non-deterministic automaton. "Non-deterministic" means that there may be a choice that must be made in processing the input string, and the choice can not be determined by looking at the current character.

A non-deterministic automaton accepts an input string if there is a path that leads to a final state with all characters consumed. There may be other paths using the same characters that lead to dead ends, but all that matters is that there is at least one path that works. A particular set of choices might lead to a dead end. But a string is accepted if there is one (or more) paths leading to a final state.


If you get stuck while processing a string with a non-deterministic automaton what must you do?