Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular 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 &gt; 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)$ 

&mdash;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?

---EDIT: SECOND TRY---

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

$x = (10)^l$

$y = (10)^m$, where $l+m \le p$ and $m &gt; 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|&lt;|b|$ and $|a|&lt;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?
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


$|xy| \leq p$
$|y| &gt; 0$
$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 &gt; 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.