I'm looking for a way to find the smallest possible regular-expression that accepts a sequence.

To make it interesting I don't want any stars(Kleene stars) and preferably no wildcards?

For instance the sequence : 'aaaaaaaa' would be accepted by 'a^8' and a^8 would be the shortest possible expression to accept the sequence.

Does anyone body know how to generate such an expression?

  • $\begingroup$ Wouldn't it be more correct to say generates and not accepts? $\endgroup$ – Logan Mayfield Aug 7 '12 at 13:24
  • 8
    $\begingroup$ You have to define the grammar of the “regular expressions” you are talking about. r^n (where r is a regular expression and n is an integer) is usually not considered as an integral part of regular expressions, at least in theoretical computer science, because it can be easily replaced by the n repetition of r. $\endgroup$ – Tsuyoshi Ito Aug 7 '12 at 14:14
  • 2
    $\begingroup$ What have you trie d? $\endgroup$ – Jeffε Aug 7 '12 at 19:01
  • $\begingroup$ @JɛffE once I have build a trie, how do I know what nodes to pick as sub expressions? $\endgroup$ – Martin Kristiansen Aug 8 '12 at 7:33

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.