Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I have gotten in my proof, but I am getting stuck when showing why it is contradicting the pumping lemma:

$s = (1^p = 1^p ⊕ 0^p)$

$x = 1^l$

$y = 1^m$, where $l+m \le p$ and $m > 0$

$z = (1^{p-l-m}=1^p ⊕ 0^p)$

Taking $i=2$, $xy^2z = (1^l1^{2m}1^{p-l-m}=1^p ⊕ 0^p) = (1^{p+m}=1^p ⊕ 0^p)$

—This is where I am getting stuck. From my example, this appears to be a contradiction, but there is nothing in the language dictating that $b$ and $c$ be of equal lengths. Were they to be different lengths, it could certainly be possible that no contradiction would be found by adding $m$ to $p$. How could I fix my proof via pumping lemma?


$s = ((10)^p = (01)^p ⊕ (10)^p)$

$x = (10)^l$

$y = (10)^m$, where $l+m \le p$ and $m > 0$

$z = ((10)^{p-l-m}=(01)^p ⊕ (10)^p)$

Taking $i=0$, $xy^0z = ((10)^l(10)^{p-l-m}=(01)^p ⊕ (10)^p) = ((10)^{p-m}=(01)^p ⊕ (10)^p)$

Now, I have that $|a|<|b|$ and $|a|<c$, which is not possible, since the result of the exclusive-or must contain a leading 1, which cannot be truncated to a smaller string length. Therefore, this is a contradiction.

Is this a contradiction strong enough to prove the language is not regular? It only works in the case of a leading 1; do I need to show something that is a contradiction even with leading 0's?

  • $\begingroup$ Try something else instead of $a = 1^p$. $\endgroup$ – Yuval Filmus Feb 9 '17 at 22:40
  • $\begingroup$ @YuvalFilmus so I'm assuming I also need a new $b$ and $c$? $\endgroup$ – tpm900 Feb 9 '17 at 22:48
  • $\begingroup$ Possibly. Just try a few things and eventually something will work out. It's not always the case that the first thing you try works. $\endgroup$ – Yuval Filmus Feb 9 '17 at 22:51
  • 1
    $\begingroup$ Please don't use "EDIT:". Instead, edit your question to read well for someone who is encountering it for the first time. Also, after the edit, what is your question? Do you have any remaining question? This is a question-and-answer site, so we require you to formulate a specific question. We don't check proofs or grade proposed solutions (talk to a TA for that). $\endgroup$ – D.W. Feb 10 '17 at 5:49
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not regular? $\endgroup$ – David Richerby Aug 10 '17 at 10:40

Suppose $L$ were regular. Let $p$ be the pumping constant assumed to exist and consider the string

$$s = 1^p = 1^p \oplus 0^p$$

Clearly, $|s| \geq p$ so for some strings $x,y,z$ we have $s = xyz$ where

  1. $|xy| \leq p$
  2. $|y| > 0$
  3. $xy^iz \in L$ for all $i \geq 0$

If condition 1 is to hold, $y$ must be a string of $1$s. If condition 2 is to also hold, then $y = 1^k$ for some $k > 0$. But then condition 3 fails, since $xy^0z \notin L$.

For $xy^0z = 1^{p-k} = 1^p \oplus 0^k$, and this identity is false irrespective of whether we require $w_1 \oplus w_2$ to be defined for strings of the same length only, or in general.


Thought A)

Perhaps your definition of "a" needs to be reworked; eg. not count all the leading zeros as significant (0000 = 0). You can substantiate this by making the case that XOR is an arithmetic operation.

In this way given an acceptor for a given length of string you could pump through another string that output the same result proving that its not regular.

010 XOR 010 = 0 and 0110 XOR 0110 = 0

Thought B)

There are no "real" contradictions for the language "a". It consists of every string of { 0,1 }* by definition. However using thought A) you can pump through multiple "definitions" of an accepted word in the language.

Thought C)

What do you think?

  • 2
    $\begingroup$ I don't really understand what you're trying to say, here. In general, we're looking for complete answers to questions but, for homeworky questions such as this one, hints are often more appropriate. Please accept my apologies if I've failed to understand what you've written, but I'm not sure that your answer is a hint. It reads more like part of a discussion between two people who don't know how to solve the problem, rather than hints from somebody who does know. $\endgroup$ – David Richerby Feb 10 '17 at 9:41
  • $\begingroup$ @JamesR, I don't seem to understand what you're saying. I deliberately chose an $a$ where there are no leading 0's, so that shortening $a$ would lead to a different value that is invalid in the context of the rest of the expression $\endgroup$ – tpm900 Feb 10 '17 at 20:51

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.