How to proof $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

  • 1
    $\begingroup$ Words of length $\le1$ are palindromes, arent't they? $\endgroup$ – Hagen von Eitzen Sep 23 '18 at 17:10
  • $\begingroup$ Yes, $\lambda$ and $0,\, 1 \in$ Palindrome $\endgroup$ – Wakeme UpNow Sep 23 '18 at 17:12

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.

  • $\begingroup$ What is your proof for a two-letter alphabet? $\endgroup$ – J.-E. Pin Sep 24 '18 at 8:16
  • $\begingroup$ My guess is you can work something out based on strings like $x_n = abaab... \underbrace{a...a}_n b$, but it takes a bit more work to show that $x_m x_k^R$ isn't a member of the language. $\endgroup$ – Chessanator Sep 24 '18 at 15:32
  • $\begingroup$ You choose $x_n=12\dots n$. Is that $n$ different symbols? I do not see how you bound $n$ here? $\endgroup$ – Hendrik Jan Sep 27 '18 at 15:58
  • $\begingroup$ $n$ different symbols is the idea, yes. If the language has infinitely many symbols then you can get $n$ different symbols for any $n$. I think my other comment works as a way to translate the idea to finitely many symbols. $\endgroup$ – Chessanator Sep 27 '18 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.