In Figs. 1.12 and 1.13 we used character sets on transitions as shorthands for sets of transitions, each with one character. We can, instead, extend the
definition of NFAs and DFAs such that such character sets are allowed on a single
transition.
For a DFA (to be deterministic), we must require that transitions out of the same
state have disjoint character sets.
a) Sketch how Algorithm 1.3 must be modified to handle transitions with sets in
such a way that the disjointedness requirement for DFAs are ensured.
b) Sketch how Algorithm 1.4 must be modified to handle character sets. A new
requirement for DFA minimality is that the number of transitions as well as the
number of states is minimal. How can this be ensured?
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here