Give a CFG for the language $\{x \in \{a,b\}^* | x \not= ww \text{ for some w} \in \{a,b\}^*$
In my attempt to do this I understand odd length strings are automatically in the language, but don't know how to handle even length strings. What would the CFG look like? I know it starts with S-> E|U when E is the even case and U the uneven case.
Thanks.
A detailed answer can be found here: not-square-words-are-context-free-and-not-regular. According to this answer, the grammar \begin{align} S &\to AB + BA + A + B \\ A &\to aAa + aAb + bAa + bAb + a \\ B &\to aBa + aBb + bBa + bBb + b \end{align} generates the set of non-square words of $\{a,b \}^*$.