10
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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$).
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – domotorp Jan 13 at 8:22
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Michaël Cadilhac Jan 13 at 11:11
  • 2
    $\begingroup$ Oh, my bad, $p/2\le |w|/3$ always holds! $\endgroup$ – domotorp Jan 13 at 20:22
  • $\begingroup$ Probably it's not an issue, but $p$ can be odd, so you should handle the cases $|u| = 3p/2 (?)$ when $p$ is odd. $\endgroup$ – Marzio De Biasi Jan 16 at 9:37
  • $\begingroup$ @MarzioDeBiasi: Yes, that's precisely why this is a sketch :-) $\endgroup$ – Michaël Cadilhac Jan 16 at 11:58
7
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.