On Feb 23, 3:48 pm, Erik de Castro Lopo wrote:
> I'm playing around with the conversion of NFAs to DFAs.
>
> I'm perfectly happy with my understanding of the difference between
> NFAs and DFAs, but as far as I can see there are at least two
> (possibly overlapping) kinds of NFAs:
>
> - NFAs with epsilon transitions, where no input symbols are
> consumed when moving from state to state on an epsilon
> transition.
>
> - NFAs which when in some state and accepting an input symbol
> can transtion to more than one state.
>
> I realise that these two are basically eqivalent and that either
> of these could be converted to the other, but I've found a couple
> of articles on the web explaining the conversion of the first type
> of NFA to a DFA, but none explaining the second.
>
> Why is that?
Since you can always change the second type of NFA to the first type
by adding some epsilon states in the right place, you can always do
the conversion to DFA via a two-step process. First change the second
type of NFA to the first type by adding the required epsilon states.
Then change the resulting NFA to a DFA using the techniques that
you've read about. That way you don't need an article explaining how
to change the second type of NFA to a DFA. I would reckon that that
is the reason that you can't find any articles on the process.
Cheers
Derek
|
