Separating Words with Small Grammars
James Currie, Holger Petersen, John Michael Robson, Jeffrey O. Shallit · 1999
We study the following problem: given two words $w$ and $x$, with $|w|,|x|\geq n$, what is the size of the smallest context-free grammar $G$ which generates exactly one of $\{wx\}$? If $|w| ot= |x|$, then we prove there exists a $G$ separating $w$ from $x$ of size $O(\log\log n)$, and this bound is best possible. If $|w|=|x|$, then we get an upper bound on the size of $G$ of $O(\log n)$, and a lower bound of $\Omega(\frac{\log n}{\log\log n})$.