Let's say my dictionary is {a,b} I want to ccind a regular expression for the languge of the words that does not contain bbb in the most minimal way. All I can think about is '+'ing between prefixes but I think that there is a way to get a shorter answer.

  • $\begingroup$ Minimal according to what measure? Also, it would help if you spelled out the regular expression you have found by your approach. $\endgroup$ Dec 25 '16 at 17:56
  • $\begingroup$ Minimal = Shortest. Mine is something like: a*+ (ab)* + (ba)* + (bb)* $\endgroup$
    – NotSure
    Dec 25 '16 at 17:58
  • $\begingroup$ Relevant but without real answer cstheory.stackexchange.com/questions/12361/… It seems like the problem is PSPACE complete. $\endgroup$
    – adrianN
    Dec 25 '16 at 17:59
  • $\begingroup$ Your RE can produce abbb, so it contains bbb. $\endgroup$
    – Evil
    Dec 25 '16 at 21:34
  • 3
    $\begingroup$ The shortest I can think of is (a + ab + abb)* $\endgroup$
    – quicksort
    Dec 26 '16 at 11:14

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.