3
$\begingroup$

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?

  • 0
    $(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$.2011-11-04
  • 0
    @HenningMakholm: You are of course right. I was thinking of $1^{(n^n)}$.2011-11-05

1 Answers 1

5

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

  • 0
    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$?2011-11-04
  • 0
    @joriki: Oops, I got myself confused while expressing the idea. Hopefully it's better now.2011-11-04
  • 0
    I think it is -- very nice! :-)2011-11-04