# What's the regex corresponding to this DFA? [duplicate]

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.

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*

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

$$(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$.
• 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. Jul 28 '16 at 23:07
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$.