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


With a deterministic automaton there is only one transition (or no transitions) out of the current state for each input symbol.


For this chapter, the automata examine strings, so each input symbol is a single character. There will be only one transition (or no transition) out of the current state for the current character. No epsilon-transitions are allowed.

It is not too hard to write a program that implements a non-deterministic automaton. However, this calls for backtracking or other search technique. This chapter does not explain those techniques.


Why is the restriction to deterministic automata not a big problem?