Explore BrainMass

Converting a regular expression to a DFA

How can a regular expression be converted into a deterministic finite automaton (DFA)?

Solution Preview

The basic approach to convert a regular expression to a DFA is to first convert the regular expression an an NFA (non-deterministic finite automaton) and then convert the NFA to a DFA. Doing this breaks the problem down into a couple of manageable states.

An NFA differs from a DFA in that there are "epsilon" states which are transitions between states with no input. There are also multiple transitions from one state to another on the same input.

In order to convert the regular expression to an NFA we use the following five rules:

1) any literal becomes an NFA that goes from the start state to final state, transitioning on the input. That is, a literal "a" in the regular expression becomes an NFA like this:

(start) ----[a]----> (final)

2) any "epsilon" in the regular expression (that is a zero length string) becomes the NFA:

(start) ...

Solution Summary

This solution walks through the steps of converting a regular expression to a DFA.