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)?

  • 4
    I'm voting to close this question as off-topic because it doesn't have anything to do with natural languages.
    – curiousdannii
    Dec 4 '19 at 11:53
  • @curiousdannii I tagged it as related to formal grammar. Did I get the meaning of the tag wrong? Dec 4 '19 at 12:31
  • 3
    It's not a linguistics question; it's a computer science question, and would be better asked in a computer-science-related stack. Dec 4 '19 at 12:52

If you generate (or parse, same thing in reverse) both of the strings at the same time, one token at a time, your grammar can only be in a limited number of states (strings are (still) the same, strings differ so the rest doesn't matter, etc.). Even though we as humans like to parse the string from left to right, the way we read it, a context-free grammar doesn't have that limitation.

I tried to keep this in the form of a hint and not a full solution. Sorry if this is too explitit and spoils the solution for you, or not enough. The above is the realisation I personally needed to be able to solve this exact problem though!

  • Thank you for your help! I had pretty similar ideas while I was trying to solve the problem on my own, yet I clearly lacked experience to finish it. Could you, please, recommend any materials which comprise problems of such sort and, perhaps, cover any similar ideas? Dec 4 '19 at 14:59

Agnes has already explained the intuition why the language is context-free. Here are three more concrete tips that may be helpful:

Define symbols for languages of arbitrary strings (a) starting with 0, (b) starting with 1, (c) ending with 0, and (d) ending with 1.

Given symbols rewriting to these strings, can you write a grammar for the language M = X2XR, where X is an arbitrary string and XR is the reverse of X?

Use M in your grammar to be the middle part of the string X2Y up to the point where X and Y differ. For example, to produce the string 0002010, M should rewrite to 020.

  • Thanks for your help! I believe, I was somehow close to solving this on my own, yet I clearly lack a lot of experience. Can you, please recommend me any materials which comprise some problems of that sort and, perhaps, cover some related topics? Dec 6 '19 at 19:08
  • 1
    @ZhiltsoffIgor I hate to disappoint but my experience doesn't reach much further than an undergraduate course. We read Thomas A. Sudkamp's Languages and Machines, which has exercises at the end of each chapter. Context-free grammars are in chapter 3; there's plenty of other stuff as well.
    – Keelan
    Dec 6 '19 at 22:15

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