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

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

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

<p>Does anyone body know how to generate such an expression?</p>

CC BY-SA 3.0
2012-08-07T13:24:40.720Z
Wouldn't it be more correct to say generates and not accepts?
Logan Mayfield
CC BY-SA 3.0
2012-08-07T14:14:01.120Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-07T19:01:25.640Z
What have you **trie** d?
Jeffε
CC BY-SA 3.0
2012-08-08T07:33:16.930Z
@JɛﬀE once I have build a trie, how do I know what nodes to pick as sub expressions?
Martin Kristiansen
<ds.algorithms><fl.formal-languages><regular-expressions>
Given a sequence find the shortest reg exp that generates it?
Martin Kristiansen
# Given a sequence find the shortest reg exp that generates it?

(Asked by: username_0 on 2012-08-07)

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?

**Tags:** ds.algorithms, fl.formal-languages, regular-expressions
> **Comments:**
> **username_1**: Wouldn't it be more correct to say generates and not accepts?  
> **username_2**: 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.  
> **username_3**: What have you **trie** d?  
> **username_0**: @JɛﬀE once I have build a trie, how do I know what nodes to pick as sub expressions?  

---

## 0 answers

