Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
are $\varepsilon$ and $\emptyset$ counted as symbols or as operations? –  Ran G. Apr 26 '12 at 4:29
    
@Ran I was counting them as symbols. –  Lucas Cook Apr 26 '12 at 5:38

1 Answer 1

up vote 28 down vote accepted

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.

share|improve this answer
    
Very cool result, and rather surprising as well :) –  Alex ten Brink Apr 26 '12 at 6:33
    
How does that regular expression look like? –  svick Apr 26 '12 at 6:51
    
@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 :) –  Alex ten Brink Apr 26 '12 at 6:57
    
@Yuval Very cool. Thanks for the reference! –  Lucas Cook Apr 26 '12 at 14:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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