7
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

Rather than directly using the pumping lemma, you can use the closure property of context-free languages.

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Toobatf
    Commented Jun 23 at 12:13
  • $\begingroup$ @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. $\endgroup$
    – pcpthm
    Commented Jun 23 at 12:24
  • 1
    $\begingroup$ I edited my answer to be correct when using left-padding. $\endgroup$
    – pcpthm
    Commented Jun 23 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.