Prove that a binary language is not regular by using the fact that the binary language of palindromes is not regular without using Pumping Lemma.

Question

Note: This is not a repeat question. There is another questions very similar to this posted, but that uses the Pumping Lemma.

A binary language of all binary strings that are palindromes $L_1$ is not regular. Use this fact to prove that $L_2$ which contains all binary strings that are not palindromes is not regular. Prove this without using Pumping Lemma.

Answer 1

HINT: If $L_2$ were regular, there would be a DFA $M$ that recognized (accepted) it. Explain how to modify $M$ so that it would recognize $L_1$. Since $L_1$ is not regular, that’s impossible, and the contradiction will prove that $L_2$ can’t be regular.