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?