Prove that a language which consists of concatenation of strings in palindromes is not a regular language? How to prove $L = \{ x \in \Sigma^* | x=y_1\cdot y_2 \cdot \dots y_m, \exists m \ge 1 \,\land \forall y_i \in \text{Palindrome over } \Sigma^*\}$ is not a regular language?
My attempted is
$\text{Let }\,y_1 = 0^a1^b0^a$. So $x = 0^a1^b0^a \cdot y_2 \cdot \dots \cdot y_m$.
Now $\text{Let } x = uvw$. $u = 0^i\, v = 0^j, w = 0^{a - i - j}1^b0^a \cdot y_2 \cdot \dots \cdot y_m$
But the problem occurred here. I can proof that $0^a1^b0^a$ is not regular but from $L$. It can split the original $0^a1^b0^a$ into 3 parts which are $0^a, \, 1^b,\,0^a$ respectively. And from the original $m$ values, it becomes $m + 2$.
So I am not sure on how to prove $L$ is not a regular language.
 A: If words of length one are palindromes then your set just consists of all (non-empty) words so is regular.
If we instead use the definition that a palindrome is a word followed by its reverse (Note that there are no even palindromes with this definition) then we can show that your language is not regular as follows. (If the language has infinitely many symbols, this is easy. The construction is harder with finitely many symbols, but should still be possible.)
Suppose for contradiction that we have a finite-state automata that recognises your language. In particular, it recognises all palindromes.
Consider the palindromes formed by taking $x_n= 12...n$ followed by the reverse. In particular, consider the state our automata is in at the final $n$ of $x_n$. There are infinitely many such strings while our automata is finite, so we must be able to find different $x_m$ and $x_k$ that are at the same state at the end.
Then $x_m x_k^R$ is recognised by the automata, as following $x_m$ takes it to that shared final state and then following $x_k^R$ takes it to the accepting state of $x_k x_k^R$.
However $x_m x_k^R$ is not a member of your language. Therefore any automata that accepts every member of your language also accepts strings outside it.
