# Regular expressions which first disagree after an exponential length

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?

-
$(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

## 1 Answer

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)$).

-
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