How can I prove that all strings in {0, 1} * that contain any palindrome of length at least 6 as a substring is regular?

529 Views Asked by At

Because palindrome is irregular, I do not know how to prove above, even if I know for example, {0^n1^n|n>0} is irregular but it is a subset of 0*1*, which is regular.

I don't think I can use, for example, shorter palindromes, length less than 6, are regular, so I can put 0 or 1 at the head and the tail to let the length of palindrome exceed 6 and infinite eventually. I don't think this could prove it is regular.

1

There are 1 best solutions below

0
On

Let $L\subseteq\{0,1\}^*$ be the language of strings that contain a palindrome substring of length at least $n$. A string has a palindrome substring of length $\ge n$ if and only if it has a palindrome substring of length either $n$ or $n+1$. This allows you to write $L=\{0,1\}^*Q\{0,1\}^*$ for some finite language $Q$. The first observation follows from the fact that, if $s$ is a palindrome string of length at least $2$, then $s$ with the first and last character removed is palindrome as well, thus establishing that if $w$ has a palindrome substring of length $m>1$, then $w$ has a palindrome substring of length $m-2$. Therefore, given $w$ a word in $L$, the least length of a palindrome substring of length $\ge n$ will be either $n+1$ or $n$.