# How to show that A is not regular?

Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “1011 = 1011 ⊕ 1011” is not

How can I show that A is not regular? How should I have the string?

Also, if the binary numbers are of fixed length, 64 bit long, would A then be regular or not?

• For your second question, if the numbers are restricted to be fixed length, show that the language $A$ is finite. Are finite languages regular or not? – Rick Decker Oct 7 at 23:51

Let us choose $$p$$ to be the pumping length. Let's now take $$0^n=1^n \oplus 1^n$$, which is in $$A$$. This string can be decomposed into three concatenated substrings $$xyz$$. Since $$|xy| \leq p$$, we see that $$v=0^k$$ for some $$k$$ greater than 0. If we choose to pump it $$i$$ times, we will then obviously obtain an $$x$$ which is longer ($$i > 1$$) or shorter ($$i = 0$$) than the other two operands and cannot then be the result of their XOR, hence proving that the language is not regular.