For each n, exhibit two regular expressions, R and S, of length poly(n), where L(R) ≠ 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 up to 2^εn for some constant ε > 0.