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

Question

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.

Answer 1

The question has been asked before, but since it's faster to describe the answer than to find the previous question, I'll outline the answer here.

We can characterize words in $L$ as belonging to one of two classes:

1. Words of odd length.

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