[Solved]: Convert RE to DFA

Problem Detail: 

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.

Asked By : AkshaiShah

Answered By : Renato Sanhueza

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}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42176