2
$\begingroup$

Here is a DFA from a research project. We created the DFA manually. We are interested in which regex is this DFA corresponding to. Certainly, there could be multiple regex corresponding to it; we prefer a simpler one.

enter image description here

Inspired by the first answer from Karolis Juodelė, one correct Answer should be:

(00*10*1|1(0*|(10)*)*110*1)*1(0*|(10)*)*110*

$\endgroup$
  • $\begingroup$ You forgot to label the loop from $E$ to $E$ - the input 0. $\endgroup$ – scaaahu Mar 29 '13 at 10:53
  • $\begingroup$ Since you did not include any of your own thoughts and particular issues, this question is completely covered by the referenced question. $\endgroup$ – Raphael Mar 31 '13 at 11:29
3
$\begingroup$

$$(00^*10^*1 ~~~ | ~~~ 10^*(10)^*110^*1)^*~~~10^*(10)^*110^*$$ This should be one representation. Not sure if it could be made simpler. The part from $($ to $|$ represents one lap in the upper cycle. The part from $|$ to $)$ represents a lap in the lower cycle. The last part represents the path from $A$ to $D$.

$\endgroup$
  • $\begingroup$ The regex as identified by Karolis (00∗10∗1 |10∗(10)∗110∗1)∗ 10∗(10)∗110∗ is of the type ((R1 | R2)1)* R2. Where R1 = 00*10* , R2 = 10*(10)*110*. $\endgroup$ – farhanhubble Mar 29 '13 at 10:39
  • $\begingroup$ Your answer is really inspiring, though there is a minor error: 0*(10)* should be (0*|(10)*)* since both 0* and (10)* can go back to node B. $\endgroup$ – JackWM Jul 28 '16 at 23:07
0
$\begingroup$

Assuming I haven't made a mistake, I get $(0^{+}10^{\ast}1)^{\ast}10^{\ast}(0^{+}1)^{\ast}10^{\ast}$ via one application of the DFA to regular expression conversion algorithm, however there are up to $5!$ possible answers as there are $5$ states to eliminate. I would assume some of these give the same answer of course. The order I happened to choose was $F, D, E, B, C$.

$\endgroup$

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