# Are Context-Free languages closed under XOR?

First, let's generalize the notion of XOR on strings over the $${0,1}$$ alphabet. For strings of the same length, the XOR is the bitwise XOR. For strings of different lengths, we define $$\text{xor}(w, \epsilon) = \text{xor}(\epsilon, w) = w$$, where $$\epsilon$$ is the empty string. Then, for any pair of strings, we can calculate the XOR by considering a bunch of $$\epsilon$$ as padding (to the left) for the shorter string. For example: $$xor(011,000011)=xor(\epsilon,000)xor(011,011)=000000$$

I wanted to first prove that context-free languages are closed under the XOR operation, but I couldn't succeed. Then, my professor gave me an example and said to try to find a context-free grammar or a pushdown automaton (PDA) for this language: $$\text{xor}(\{0^n1^{2n}\}, \{0^{2k}1^k\})$$. I couldn't find such a grammar, but I thought that maybe it is not context-free.

I considered a special case where $$m = n$$. In this case, we have $$0^n1^n0^n$$, which is not context-free. However, this is just a special case. I also tried to find a suitable string for the pumping lemma, so I guessed that $$0^n1^n0^n$$ probably is a good candidate, but I couldn't pump this string to reach a string that cannot be the XOR of $$\{0^n1^{2n}\}$$ and $$\{0^{2k}1^k\}$$. Am I choosing the right candidate? Why can't I reach such a string that is not in the language?

I use $$L_1 := \{1^{2n}0^n \mid n \geq 0\}$$ and $$L_2 := \{1^n0^{2n} \mid n \geq 0\}$$ to show $$L := \mathrm{xor}(L_1, L_2)$$ is not context-free. These are just the reverse of your languages.
Let $$R = 0^* (0|1)$$ be a regular language and consider the intersection $$L' := L \cap R$$. If $$L$$ is context-free, then its intersection with a regular language must be context-free as well.
However, you can prove that $$L'$$ is equal to the non-context-free language $$\{0^n1^n0^n \mid n \geq 1\}$$ because if two strings of xor operands have different lengths, then the first character will be a 1.
• This is not the case. Consider $n = 1$ and $k = 2$. Then we have $\text{xor}(011, 000011) = \text{xor}(\epsilon, 000) \text{xor}(011, 011) = 000000$, which contradicts your assumption that if the last character is $0$, then $m = n$. Commented Jun 23 at 12:13
• @Toobatf I assumed xor was right-padded like xor(001, 000011) = xor(0010000, 000011). But if you use left-padding, just reverse all the languages. Commented Jun 23 at 12:24