CODEWITHSUNDEEP
regexsequence
Martin Kristiansen
Martin Kristiansen

Reputation: 10222

How do I find the shortest possible reg exp that accepts a sequence?

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?

Upvotes: 0

Views: 196

Answers (2)

Lars Kotthoff
Lars Kotthoff

Reputation: 109242

Given that regular expressions and deterministic finite automata are equivalent, you can minimise a given regular expression using any of the algorithms for the minimisation of DFAs. You would of course still need to come up with a regular expression to start with, but if you only need it to accept one string, then the characters of that string are the states. You can then minimise that DFA and convert it to a regular expression.

Upvotes: 2

npinti
npinti

Reputation: 52185

The search space for what you are after will most likely grow exponentially as the string grows, since there is usually a large amount of regular patterns that can match a given string.

I think that in your case you could try using some search heuristic to try and approximate or even manage to find the optimal solution. I do not think that there is a straightforward solution for that (albeit that is just my opinion).

Upvotes: 2

Related Questions