Here's a conjecture for regular expressions:

For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| = 2$

Conjecture: If $|R| > 1$ and $L(R)$ contains every string of length $|R|$ or less, then $L(R) = \Sigma^*$.

That is, if $L(R)$ is 'dense' up to $R$'s length, then $R$ actually generates everything.

Some things that may be relevant:

  1. Only a small part of $R$ is needed to generate all strings. For example in binary, $R = (0 \cup 1)^* \cup S$ will work for any $S$.
  2. There needs to be a Kleene star in $R$ at some point. If there isn't, it will miss some string of size less than $|R|$.

It would be nice to see a proof or counterexample. Is there some case where it's obviously wrong that I missed? Has anyone seen this (or something similar) before?

  • $\begingroup$ are $\varepsilon$ and $\emptyset$ counted as symbols or as operations? $\endgroup$
    – Ran G.
    Apr 26, 2012 at 4:29
  • $\begingroup$ @Ran I was counting them as symbols. $\endgroup$
    – Lucas Cook
    Apr 26, 2012 at 5:38

1 Answer 1


Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-line, a talk is.

In the paper, they define the measure $|\mathrm{alph}(R)|$, which is the number of symbols in $R$, not counting $\epsilon$ or $\emptyset$. However, $\emptyset$ can be eliminated from every expression not generating the empty language, and the expression can be "cleaned up" so that the number of $\epsilon$ it contains is at most $|\mathrm{alph}(R)|$ (Lemma on page 10 of the talk).

In page 51, for every $n \geq 3$ they construct a regular expression of size $O(n)$ over $\{0,1\}$ which generates all strings of size at most $\Omega(2^n n)$, but doesn't generate all strings. Note that "size" here is both in your sense and theirs, since we're using big-O notation. They also pose an open question to find the best dependence between the two parameters.

  • 1
    $\begingroup$ Very cool result, and rather surprising as well :) $\endgroup$ Apr 26, 2012 at 6:33
  • $\begingroup$ How does that regular expression look like? $\endgroup$
    – svick
    Apr 26, 2012 at 6:51
  • $\begingroup$ @svick: it cleverly combines the trick that $(a+b)(c+d)=ac+bc+ad+bd$ with Kleene stars to capture common substrings, judging by a quick skim of the proof. The expression is quite monstrous :) $\endgroup$ Apr 26, 2012 at 6:57
  • $\begingroup$ @Yuval Very cool. Thanks for the reference! $\endgroup$
    – Lucas Cook
    Apr 26, 2012 at 14:54
  • 2
    $\begingroup$ @YuvalFilmus It seems like the paper is available online now. $\endgroup$ Feb 16, 2016 at 8:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.