This is a question that's been bugging me off and on for years, ever since I took a compiler theory class as an undergraduate. There, we learned how to convert a regular expression into a non-deterministic finite automaton, then convert that into a deterministic finite state machine, then minimize that state machine. It was also mentioned in passing that there's a transformation in the opposite direction, but that wasn't covered as not practically useful for our purposes.

In the introduction to finite state machines, on the other hand, one of the examples given was an analysis of the classic children's puzzle to bring a dog, a cat, and a mouse across a river in a small rowboat. It's not hard to list the valid reachable states in this puzzle and construct a finite state machine like this (where dcm*| is the initial state and |dcm* is the only accepting state): Dog-Cat-Mouse Puzzle Finite State Machine

So, putting these two together, it led me to the question in the title: what's a corresponding regular expression for valid solutions to the puzzle? All the possible loops mean I quickly get bogged down in any attempt to construct a regular expression which covers all cases.

OK, I'm now led to this answer by the suggested links appearing as I'm typing this question: How to convert finite automata to regular expressions? . However, if I try any of the algorithms suggested there, I quickly get an exponential explosion of terms. So, I guess a possible answer would be "this is a pathological case which probably doesn't have any answer shorter than $2^{10}$ or so symbols" if that's indeed correct.

  • $\begingroup$ For this puzzle, the "return" edges of loops are redundant and can be ignored safely. Hence, in my opinion, the regular expression is $c0(dcm|mcd)0c$ (if I am correct in the syntax). $\endgroup$ – hengxin Apr 7 '17 at 3:24
  • $\begingroup$ @hengxin No, I specifically want a regular expression which accepts any amount of useless backtracking, so it must accept e.g. c000dcmdcmdccdmcd0ccc. $\endgroup$ – Daniel Schepler Apr 7 '17 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.