This problem was taken from A. Shen's book "Algorithms and Programming. Problems and Solutions". The problem itself was communicated by M. Sipser.
The author asks the reader to define a context-free grammar which generates the following language:
{X2Y | X ∈ {0, 1}*, Y ∈ {0, 1}*, X ≠ Y}.
First of all, I cannot understand how such a language could be context-free (looking from my newbie-perspective):
Both X and Y can be any sequence whatsoever, but they cannot be one sequence at the same time. This seems like a context-sensitive property to me.
What is the real meaning behind the terms "context-free" and "context-sensitive", which does not contradict the language above being context-free? How can one construct such a grammar (I would really appreciate a hint instead of a full solution)?
Since you asked for a hint, I'll give you a hint rather than writing the whole answer out. The difficulty here is that we need X and Y to be different strings. We know that X2Y with X and Y the same is NOT context-free. This is because we have |X| = |Y| things to check - the first symbols match, the second symbols match, etc. However, if X and Y must be different, we only need to guarantee they differ in at least ONE place. If we can guarantee they differ in symbol number N, then we have guaranteed X and Y are different. Can you write a context-free grammar that generates (0+1)^n 0 (0+1)* 2 (0+1)^n 1 (0+1)*? If so, the answer to your question is the union of that CFG's language and the language of the one that has the mismatched symbols exchanged (so 1 comes first, then 0).