Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?

I've tried to intersect $L$ with $a^*b^*a^*b^*$, but I still can't prove anything. I also looked at Parikh's theorem, but it doesn't help.


2 Answers 2


It's context-free. Here's the grammar:

$S \to A | B|AB|BA$
$A \to a|aAa|aAb|bAb|bAa$
$B \to b|aBa|aBb|bBb|bBa$

$A$ generates words of odd length with $a$ in the center. Same for $B$ and $b$.

I'll present a proof that this grammar is correct. Let $L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ (the language in the question).

Theorem. $L = L(S)$. In other words, this grammar generates the language in the question.

Proof. This certainly holds for all odd-length words, since this grammar generates all odd-lengths words, as does $L$. So let's focus on even-length words.

Suppose $x \in L$ has even length. I'll show that $x \in L(G)$. In particular, I claim that $x$ can be written in the form $x=uv$, where both $u$ and $v$ have odd length and have different central letters. Thus $x$ can be derived from either $AB$ or $BA$ (according to whether $u$'s central letter is $a$ or $b$). Justification of claim: Let the $i$th letter of $x$ be denoted $x_i$, so that $x = x_1 x_2 \cdots x_n$. Then since $x$ is not in $\{ww \mid w \in \{a,b\}^{n/2}\}$, there must exist some index $i$ such that $x_i \ne x_{i+n/2}$. Consequently we can take $u = x_1 \cdots x_{2i-1}$ and $v = x_{2i} \cdots x_n$; the central letter of $u$ will be $x_i$, and the central letter of $v$ will be $x_{i+n/2}$, so by construction $u,v$ have different central letters.

Next suppose $x \in L(G)$ has even length. I'll show that we must have $x \in L$. If $x$ has even length, it must be derivable from either $AB$ or $BA$; without loss of generality, suppose it is derivable from $AB$, and $x=uv$ where $u$ is derivable from $A$ and $v$ is derivable from $B$. If $u,v$ have the same lengths, then we must have $u\ne v$ (since they have different central letters), so $x \notin \{ww \mid w \in \{a,b\}^*\}$. So suppose $u,v$ have different lengths, say length $\ell$ and $n-\ell$ respectively. Then their central letters are $u_{(\ell+1)/2}$ and $v_{(n-\ell+1)/2}$. The fact that $u,v$ have different central letters means that $u_{(\ell+1)/2} \ne v_{(n-\ell+1)/2}$. Since $x=uv$, this means that $x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2}$. If we attempt to decompose $x$ as $x=ww'$ where $w,w'$ have the same length, then we'll discover that $w_{(\ell+1)/2} = x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2} = w'_{(\ell+1)/2}$, i.e., $w\ne w'$, so $x \notin \{ww \mid w \in \{a,b\}^*\}$. In particular, it follows that $x \in L$.

  • 2
    $\begingroup$ I've edited the answer to provide a proof of correctness for this grammar, based upon the hint/sketch given by Evgeny Eltishev. Hopefully it should be clearer now why this works. $\endgroup$
    – D.W.
    Commented Dec 23, 2013 at 4:45
  • $\begingroup$ Can it generate "aabb" ? $\endgroup$ Commented Nov 22, 2015 at 16:36
  • 3
    $\begingroup$ @manasij7479 Yes: $S \to AB \to aB \to a(aBb) \to aabb$. $\endgroup$
    – J.-E. Pin
    Commented Feb 16, 2016 at 13:01
  • $\begingroup$ I have a dumb question: if I choose a word $w$ and repeat it thrice $www$, clearly this does not belong to $\{ ww | w \in \{a,b\}^* \}$ and so it belongs to the given $L$ (which you proved to be a CFL). But this means a PDA can recognize such a string? But that seems wrong though... $\endgroup$ Commented Jan 28, 2021 at 15:56
  • 1
    $\begingroup$ @sprajagopal The language would not only recognize www, so it’s useless. Consider the language of all words (Z*), which also includes www. $\endgroup$
    – HappyFace
    Commented May 5, 2022 at 11:26

This language is context free it was proved in the following paper:

Tomaszewski, Zach. "A Context-Free Grammar for a Repeated String." Journal of Information and Computer Science, 2012 (PDF).

The grammar is as follows: \begin{align*} S&\to E\mid U\mid \epsilon\\ E&\to AB\mid BA\\ A&\to ZAZ\mid a\\ B&\to ZBZ\mid b\\ U&\to ZUZ\mid Z\\ Z&\to a\mid b \end{align*}

  • 9
    $\begingroup$ Welcome! The following is not a criticism of this answer. The Journal of Information and Computer Science is published by "World Academic Union", which is on Beall's list of predatory open access publishers. It's sad that there are companies in the world who will take relatively large amounts of people's money to publish papers that do nothing more than solve undergraduate-level exercises. $\endgroup$ Commented Jun 27, 2016 at 9:01
  • $\begingroup$ I don't have enough reputation to comment on the above answer. But that grammar seems wrong to me. It cannot generate "aaab" which is in the language. $\endgroup$ Commented Jun 28, 2016 at 2:23
  • 1
    $\begingroup$ After performing $CFG \to CNF \to CYK$ (you should try it), $S\to AB\to aAaB\to aaaB\to aaab$, so it seems it can generate $aaab$. $\endgroup$
    – Evil
    Commented Jun 28, 2016 at 5:09
  • $\begingroup$ You right it does $\endgroup$ Commented Jun 28, 2016 at 5:12
  • 1
    $\begingroup$ How does the PDA of this grammar look like? It seems to accept all strings $w^k$ except $k=2$. So it has a way to detect $ww$? Which seems impossible for a PDA to do (since no PDA can recognize $ww$). $\endgroup$ Commented Feb 2, 2021 at 13:21

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