Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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*
$$(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$.
0*(10)* should be (0*|(10)*)* since both 0* and (10)* can go back to node B.
$\endgroup$
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$.
