# CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language:

$L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ww\}$ with $\Sigma = \{a,b\}$

I am trying some rules of the form

$L \Rightarrow a | b$

$S \Rightarrow aSbS\ |\ bSaS\ |\ L\ |\ ab\ |\ ba$

However this is wrong since for example the grammar does not accept 3-symbol strings. I am a little bit stuck with it so any help would be greatly appreciated.

## marked as duplicate by Raphael♦Feb 9 '16 at 12:19

We can characterize words in $L$ as belonging to one of two classes:
2. Words $z_1 \ldots z_n w_1 \ldots w_n$ where $z_i \neq w_i$ for some $i$.
It is easy to generate words of the first type. As for words of the second type, for fixed $i$ and $n$ we can generate them using rules of the form $\Sigma^{i-1} a \Sigma^{n-i} \Sigma^{i-1} b \Sigma^{n-i} = \Sigma^{i-1} a \Sigma^{i-1} \Sigma^{n-i} b \Sigma^{n-i}$ and its counterpart with $a,b$ replaced by $b,a$. I'll let you figure out how to generate all of these words (for all $i,n$).
• "The question has been asked before, but since it's faster to describe the answer than to find the previous question" -- you really have to learn to use the site's search one of these days. ;D Google with site:cs.stackexchange.com is usually quite good. – Raphael Feb 9 '16 at 12:20