# Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving:

, which looks correct.

I am then using subset construction to create the DFA from the NFA, shown here.

But this does not look correct to me, as for example 0 followed by 0 is not valid according to the DFA I have constructed. I was wondering how should I be modelling the epsilon in the original regular expression, as I have simply treated it as a normal epsilon.

• "subset construction" -- you mean powerset construction.
– Raphael
May 6 '15 at 6:59
• @Raphael powerset and subset can be used interchangeably. May 6 '15 at 8:51

I transformed your NFA into a DFA as an exercise for my future test.

$\epsilon-closure\{S_0\}= \{S_0,S_1,S_3,S_4,S_5,S_6,S_7,S_9,S_{12}\}= A$

$1)$ From $A$ consuming $0$: $\{S_2, S_8 ,S_{13}\}$

$\epsilon-closure\{S_2, S_8 ,S_{13}\}= \{S_2,S_5,S_6,S_7,S_8,S_9,S_{11},S_{12},S_{13}\}=B$

From $A$ consuming $1$: $\{S_{10}\}$

$\epsilon-closure\{S_{10}\}= \{S_6,S_7,S_9,S_{10},S_{11},S_{12}\}=C$

$2)$ From $B$ consuming $0$: $\{S_2, S_8 ,S_{13}\}$

$\epsilon-closure\{S_2, S_8 ,S_{13}\}= B$

From $B$ consuming $1$: $\{S_{10}\}$

$\epsilon-closure\{S_{10}\}=C$

$3)$ From $C$ consuming $0$: $\{S_8 ,S_{13}\}$

$\epsilon-closure\{S_8 ,S_{13}\}= \{S_6,S_7,S_8,S_9,S_{11},S_{12},S_{13}\}=D$

From $C$ consuming $1$: $\{S_{10}\}$

$\epsilon-closure\{S_{10}\}= C$

$4)$ From $D$ consuming $0$: $\{S_8 ,S_{13}\}$

$\epsilon-closure\{S_8 ,S_{13}\}= D$

From $D$ consuming $1$: $\{S_{10}\}$

$\epsilon-closure\{S_{10}\}= C$

Then the initial state of the DFA is $A$ because it contain $S_0$.

The final states of the DFA are $B$ and $D$ because they contain $S_{13}$.

• Nice job. This is about as clear as can be, given the complexity of the original problem. May 6 '15 at 1:35
• It appears to me that one can collapse the final states into each other and the non-final states into each other.
– user12859
May 6 '15 at 7:35
• @RickyDemer, this just gives a DFA. If you want the minimal one, that is another step. Dec 22 '15 at 14:27