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.

You’ve omitted an absolutely essential piece of information: what is the language $L_2$? — Brian M. Scott, Oct 05 '16 at 02:48
@BrianM.Scott L2 is a binary language of any binary string that is not a palindrome. — Tommy, Oct 05 '16 at 14:37
This is a question-and-answer site, not a place to copy-paste an exercise-style problem statement and expect someone to solve it for you. As such, you must articulate a specific question. I don't see a question here, just a demand for someone to do a task for you (and that's not appropriate). Please see http://meta.math.stackexchange.com/q/9959/14578 and edit your question accordingly, including to provide context as described there. — D.W., Oct 05 '16 at 16:47

score 1 · Answer 1 · answered Oct 05 '16 at 17:13

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.

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.

1 Answers1