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
    @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
    I think it is -- very nice! :-)2011-11-04