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

enter image description here

, which looks correct.

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

enter image description 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.

  • $\begingroup$ "subset construction" -- you mean powerset construction. $\endgroup$
    – Raphael
    May 6 '15 at 6:59
  • $\begingroup$ @Raphael powerset and subset can be used interchangeably. $\endgroup$
    – AkshaiShah
    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}\}$


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

enter image description here

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.