Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Problem 8.24 of Sipser's Introduction to the Theory of Computation asks:

For each $n$, exhibit two regular expressions $R$ and $S$ of length $poly(n)$ where $L(R)\not =L(S)$, but where the first string on which they differ is exponentially long. In other words, $L(R)$ and $L(S)$ must be different, yet agree on all strings of length $2^{\epsilon n}$ for some constant $\epsilon > 0$.

If we can use non-standard "regular" expressions which allow exponentiation, it's easy: e.g. $(1^{n})^n$ and $(1^{n})^{n-1}$ first disagree on a string which has length $O(n^n)$. I've been trying to play around with stars in an analogous way, but that hasn't gotten me anywhere.

Any hints?

share|cite|improve this question
$(1^n)^n$ wants the input to have length $n^2$, but $(1^n)^{n−1}$ wants the input to have length $n^2−n$. Disagreement on length $n^2−n$, which is much less than $n^n$. – Henning Makholm Nov 4 '11 at 22:04
@HenningMakholm: You are of course right. I was thinking of $1^{(n^n)}$. – Xodarap Nov 5 '11 at 1:44
up vote 5 down vote accepted

Hint: The expression $$(\underbrace{11\cdots1}_{p\text{ times}})^*1\underbrace{1?1?\cdots1?}_{p-2\text{ times}}$$ recognizes $1^k$ for every $k$ that is not a multiple of $p$.

Can you construct a polynomial-length regular expression that recognizes $1^k$ for every $k$ except ones that are multiples of all of the first $n$ primes?

(Useful knowledge: The $n$th prime is less than $n(\ln n+\ln\ln n)$ for $n\ge 6$, so the sum of the first $n$ primes is $O(n^2\log n)$).

share|cite|improve this answer
How would that help? The first number that isn't a multiple of any of the first $n$ primes is of order $(n\log n)^2$, which doesn't grow exponentially with $n$? – joriki Nov 4 '11 at 20:22
@joriki: Oops, I got myself confused while expressing the idea. Hopefully it's better now. – Henning Makholm Nov 4 '11 at 20:28
I think it is -- very nice! :-) – joriki Nov 4 '11 at 22:34

Your Answer


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.