Is the complement of { www | … } context-free?

Question

It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?

Answer 1

Still CFL I believe, with an adaptation of the classical proof. Here's a sketch.

Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the words of length not $0$ mod $3$ removed.

Let $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$. Clearly, $L'$ is CFL, since you can guess a position $p$ and consider that $u$ ends $p/2$ after that. We show that $L = L'$.

• $L \subseteq L'$: Let $w = xyz \in L$. Assume there's a $p$ such that $x_p \neq y_p$. Then write $u$ for the $3p/2$ first characters of $w$, and $v$ for the rest. Naturally, $u_{2|u|/3} = x_p$. Now what is $v_{|v|/3}$? First:

$$|v|/3 = (|w| - 3p/2)/3 = |w|/3 - p/2.$$

Hence, in $w$, this is position: $$|u|+|v|/3 = 3p/2 + |w|/3 - p/2 = |w|/3 + p,$$ or, in other words, position $p$ in $y$. This shows that $u_{2|u|/3} = x_p \neq y_p = v_{|v|/3}$.

If $y_p \neq z_p$, then let $u$ be the first ${3\over2}(|w|/3 + p)$ characters of $w$, so that $u_{2|u|/3}$ is $y_p$; $v$ is the rest of $w$. Then: $$|u| + |v|/3 = 2|w|/3 + p$$ hence similarly, $v_{|v|/3} = z_p$.

• $L' \subseteq L$: We reverse the previous process. Let $w = uv \in L'$. Write $p = 2|u|/3$. Then: $$p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$$ Thus $w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$, and $w \in L$ (since if $w$ is of the form $xxx$, it must hold that $w_p = w_{p+|w|/3}$ for all $p$).

Answer 2

Here is the way I think about solving this problem, with a PDA. In my opinion, it's intuitively clearer.

A word $x$ is not of the form $www$ iff either (i) $|x| \not\equiv 0$ (mod 3), which is easy to check, or (ii) there is some input symbol $a$ that differs from the corresponding symbol $b$ that occurs $|w|$ positions later.

We use the usual trick of using the stack to maintain an integer $t$ by having a new "bottom-of-stack" symbol $Z$, storing the absolute value $|t|$ as the number of counters on the stack, and sgn($t$) by the state of the PDA. Thus we can increment or decrement $t$ by doing the appropriate operation.

The goal is to use nondeterminism to guess the positions of the two symbols you are comparing, and use the stack to record $t := |x|-3d$, where $d$ is the distance between these two symbols.

We accomplish this as follows: increment $t$ for each symbol seen until the first guessed symbol $a$ is chosen, and record $a$ in the state. For each subsequent input symbol, until you decide you've seen $b$, decrement $t$ by $2$ ($1$ for the input length and $-3$ for the distance). Guess the position of the second symbol $b$ and record whether $a \not= b$. Continue incrementing $t$ for subsequent input symbols. Accept if $t = 0$ (detectable by $Z$ at top) and $a \not= b$.

The nice thing about this is that it should be completely clear how to extend this to arbitrary powers.

Answer 3

Just a different ("grammar oriented") perspective to prove that the complement of $\{ w^k \}$ is CF for any fixed $k$ using closure properties.

First note that in the complement of $\{ w^k \}$ there is always $i$ such that $w_i \neq w_{i+1}$. We focus on $w_1 \neq w_2$ and start with a simple CF grammar that generates:

$L = \{\underbrace{a00...0}_{w_1} \; \underbrace{b00...0}_{w_2} ... \underbrace{000...0}_{w_k} \mid |w_i|=n \} = \{ a 0^{n-1} \, b 0^{n(k-1)-1} \}$

E.g. for $k = 3$, we have $L = \{ a\,b\,0, a0\,b0\,00, a00\,b00\,000, ...\}$, $G_L = \{ S \to ab0 | aX00, X \to 0X00 | 0b0 \}$

Then apply closure under inverse homomorphism, and union:

First homomorphism: $\varphi(1) \to a, \varphi(0) \to b, \varphi(1)\to 0, \varphi(0) \to 0 $

Second homomorphism: $\varphi'(0) \to a, \varphi'(1) \to b, \varphi'(1)\to 0, \varphi'(0) \to 0$

$L' = \varphi^{-1}(L) \cup \varphi'^{-1}(L)$ is still context free

Apply closure under cyclic shifts to $L'$ to get the set of strings of length $kn$ not of the form $w^k$:

$L'' = Shift(L') = \{ u \mid u \neq w^k \land |u| = kn \}$.

Finally add the regular set of strings whose length is not divisible by $k$ in order to get exactly the complement of $\{w^k\}$:

$L'' \cup \{\{0,1\}^n\mid n \bmod k \neq 0\} = \{ u \mid u \neq w^k\}$