How can I prove that "non-palindromes starting with 010" is not a regular language?

Question

So, I have a language L in an alphabet $\{0, 1\}$ with each word starting with 010 and not being a palindrome. How can I prove that it is not regular?

I've tried to use pumping lemma, but couldn't make it work.

Answer 1

Hint/Sketch of proof: The complementary language, i.e. language of strings which either do not start by "$010$" or are palindromes, can be shown not to be regular by using pumping lemma. It's roughly in the same proof you do when you show that the language of palindrome strings is not regular.

The idea: Pick $L$ said language, $n$ as in pumping lemma. Pick a string $w\in L$ such that:

1. $w$ is palindrome
2. $w$ starts (and therefore ends) with "$010$"
3. the length of $w$ is $\ge 10n$ (say)

So write $w=uvx$ as in pumping lemma. The idea is that, if $w=010z$, then $uv^ix=010z'$ as well, whatever the decomposition. Now, if you choose appropriately $w$ satisfying (1),(2),(3) you can find one such that $uv^ix$ cannot be palindrome.

Answer 2

HINT: For each $n\in\Bbb Z^+$ let $w_n=01(01)^n1$: $w_1=01011$, $w_2=0101011$, $w_3=010101011$, and so on. Similarly, let $z_n=(01)^n0$. Show that $w_mz_n$ is a palindrome if and only if $m=n$, and apply the Myhill-Nerode theorem.