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

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^*\}$$?

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$$).
• Wow, incredible! I don't claim that I've followed every detail of your argument, like I don't see what you mean by the last line ('For the last bit'), or why you don't separate the case when $|w|/3<p/2$, but your solution does work eventually. I would summarize the main trick as $3a+3b=2a+(b-a)+2a+2b$. The similar trick also works for the complement of any $L_r=\{w^r\}$. I wonder whether $L' = \{xyz : |x|=|y|=|z| \land (x \neq y)\}$ is context-free or not. – domotorp Jan 13 at 8:22
• @domotorp: Cheers! Alright, "the last bit" was unnecessary, thanks! As for "the case when $|w|/3 < p/2$", I'm not sure where you mean that. Did I miss something? As for your $L'$, I wondered the same doing this "proof"! Not sure yet :) – Michaël Cadilhac Jan 13 at 11:11
• Oh, my bad, $p/2\le |w|/3$ always holds! – domotorp Jan 13 at 20:22
• Probably it's not an issue, but $p$ can be odd, so you should handle the cases $|u| = 3p/2 (?)$ when $p$ is odd. – Marzio De Biasi Jan 16 at 9:37
• @MarzioDeBiasi: Yes, that's precisely why this is a sketch :-) – Michaël Cadilhac Jan 16 at 11:58

Here is the way I think about solving this problem. 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.

• Indeed, very neat! – domotorp Jan 21 at 11:40
• Ah, much nicer indeed :-) – Michaël Cadilhac Feb 6 at 14:24

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\}$$