Why is $L=\{xww^r \mid \text{ $x$, $w$ belongs to }(a+b)^+) \}$ not regular?

Question

If I have a language $L$ such that $L= \{xww^r \mid \text{ $x$ and $w$ belong to }(a+b)^+) \}$.

Then can't we write regular expression for this to be $(a+b)^+(ab+ba)$?
What's wrong in this regular expression ?

Also what if I have $L= \{wxw^r \mid \text{$x$ and $w$ belong to }(a+b)^+) \}$ or $L=\{ww^rx \mid \text{$x$ and $w$ belongs to }(a+b)^+) \}$

Does the position of $x$ affect the nature of the language ?

Answer 1

Hint. Take $x = w = a$. Does $xww^r$ match your regular expression?

Answer 2

HINT: J.-E. Pin has suggested why your regular expression doesn’t generate $L$. To prove that $L$ isn’t regular (and hence that no regular expression generates $L$), you can use the pumping lemma. If $p$ is the pumping length, let $w=a(ab)^p(ba)^p\in L$. If $L$ were regular, there would be a decomposition $w=xyz$ of $w$ such that $|y|\ge 1$, $|xy|\le p$, and $xy^kz\in L$ for all $k\ge 0$. Since $1\le |xy|\le p$, while $|a(ab)^p|=2p+1$, we know that $xy$ has the form $a(ab)^\ell$ or $a(ab)^\ell a$ for some $k\ge 0$.

• Determine the possible forms of $y$.
• Then show that no matter what form $y$ has, the word $xz=xy^0z\notin L$.