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

<p>A word <span class="math-container">$x$</span> is not of the form <span class="math-container">$www$</span> iff either (i) <span class="math-container">$|x| \not\equiv 0$</span> (mod 3), which is easy to check, or (ii) there is some input symbol <span class="math-container">$a$</span> that differs from the corresponding symbol <span class="math-container">$b$</span> that occurs <span class="math-container">$|w|$</span> positions later.  </p>

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

<p>The goal is to use nondeterminism to guess the positions of the two symbols you are comparing, and use the stack to record <span class="math-container">$t := |x|-3d$</span>, where <span class="math-container">$d$</span> is the distance between these two symbols.  </p>

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

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

CC BY-SA 4.0
2019-01-21T11:40:46.127Z
Indeed, very neat!
domotorp
CC BY-SA 4.0
2019-02-06T14:24:06.097Z
Ah, much nicer indeed :-)
Michaël Cadilhac
CC BY-SA 4.0
2019-01-21T11:21:55.940Z
2019-11-24T21:46:05.877Z
2019-11-24T21:46:05.877Z
Jeffrey Shallit
<p>Just a different ("grammar oriented") perspective to prove that the complement of <span class="math-container">$\{ w^k \}$</span> is CF for any fixed <span class="math-container">$k$</span> using closure properties.</p>

<p>First note that in the complement of <span class="math-container">$\{ w^k \}$</span> there is always <span class="math-container">$i$</span> such that <span class="math-container">$w_i \neq w_{i+1}$</span>. We focus on <span class="math-container">$w_1 \neq w_2$</span> and start with a simple CF grammar that generates:</p>

<p><span class="math-container">$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} \}$</span> </p>

<p>E.g. for <span class="math-container">$k = 3$</span>, we have <span class="math-container">$L = \{ a\,b\,0, a0\,b0\,00, a00\,b00\,000, ...\}$</span>, <span class="math-container">$G_L = \{
S \to ab0 | aX00, X \to 0X00 | 0b0 \}$</span></p>

<p>Then apply closure under <em>inverse homomorphism</em>, and <em>union</em>:</p>

<p>First homomorphism: <span class="math-container">$\varphi(1) \to a, \varphi(0) \to b, \varphi(1)\to 0, \varphi(0) \to 0 $</span></p>

<p>Second homomorphism: <span class="math-container">$\varphi'(0) \to a, \varphi'(1) \to b, \varphi'(1)\to 0, \varphi'(0) \to 0$</span></p>

<p><span class="math-container">$L' = \varphi^{-1}(L) \cup \varphi'^{-1}(L)$</span>  is still context free</p>

<p>Apply closure under <em>cyclic shifts</em> to <span class="math-container">$L'$</span> to get the set of strings of length <span class="math-container">$kn$</span> not of the form <span class="math-container">$w^k$</span>: </p>

<p><span class="math-container">$L'' = Shift(L') = \{  u \mid u \neq w^k \land |u| = kn \}$</span>.</p>

<p>Finally <em>add the regular set</em> of strings whose length is not divisible by <span class="math-container">$k$</span> in order to get exactly the complement of <span class="math-container">$\{w^k\}$</span>:</p>

<p><span class="math-container">$L'' \cup \{\{0,1\}^n\mid n \bmod k \neq 0\} = \{  u \mid u \neq w^k\}$</span></p>

CC BY-SA 4.0
2019-02-01T18:23:39.370Z
2019-02-01T20:27:29.180Z
2019-02-01T20:27:29.180Z
Marzio De Biasi
<p>Still CFL I believe, with an adaptation of the classical proof.  Here's a sketch.</p>

<p>Consider <span class="math-container">$L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$</span>, which is the complement of <span class="math-container">$\{www\}$</span>, with the words of length not <span class="math-container">$0$</span> mod <span class="math-container">$3$</span> removed. </p>

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

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

<p><span class="math-container">$$|v|/3 = (|w| - 3p/2)/3 = |w|/3 - p/2.$$</span></p>

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

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

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

CC BY-SA 4.0
2019-01-13T08:22:39.177Z
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
CC BY-SA 4.0
2019-01-13T11:11:53.353Z
@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
CC BY-SA 4.0
2019-01-13T20:22:05.293Z
Oh, my bad, $p/2\le |w|/3$ always holds!
domotorp
CC BY-SA 4.0
2019-01-16T09:37:59.530Z
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
CC BY-SA 4.0
2019-01-16T11:58:27.503Z
@MarzioDeBiasi: Yes, that's precisely why this is a sketch :-)
Michaël Cadilhac
CC BY-SA 4.0
2019-01-12T23:25:37.720Z
2019-01-13T11:04:11.727Z
2019-01-13T11:04:11.727Z
Michaël Cadilhac
<p>It is well-known that the complement of <span class="math-container">$\{ ww \mid w\in \Sigma^*\}$</span> is context-free. But what about the complement of <span class="math-container">$\{ www \mid w\in \Sigma^*\}$</span>?</p>

CC BY-SA 4.0
2019-01-24T22:11:58.217Z
I've discovered that this is Theorem 4 in P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, M. Katsura: Formal languages consisting of primitive words. https://link.springer.com/chapter/10.1007/3-540-57163-9_15
domotorp
<fl.formal-languages><context-free>
Is the complement of { www | … } context-free?
domotorp
# Is the complement of { www | … } context-free?

(Asked by: username_0 on 2019-01-12)

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

**Tags:** fl.formal-languages, context-free

> **Comments:**
> **username_0**: I've discovered that this is Theorem 4 in P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, M. Katsura: Formal languages consisting of primitive words. https://link.springer.com/chapter/10.1007/3-540-57163-9_15  

---

## 3 answers

### Answer by username_2 on 2019-01-12. Score: 11 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: @username_0: 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 :)  
> **username_0**: Oh, my bad, $p/2\le |w|/3$ always holds!  
> **username_3**: Probably it's not an issue, but $p$ can be odd, so you should handle the cases $|u| = 3p/2 (?)$ when $p$ is odd.  
> **username_2**: @MarzioDeBiasi: Yes, that's precisely why this is a sketch :-)  

---

### Answer by username_1 on 2019-01-21. Score: 10

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.

> **Comments:**
> **username_0**: Indeed, very neat!  
> **username_2**: Ah, much nicer indeed :-)  

---

### Answer by username_3 on 2019-02-01. Score: 5

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


---

