Approach to finding the context free grammar of more complicated languages

Question

I'm having problems approaching the following problem.

Give a context free grammar for the following language:

{x#y | x,y in {0,1}* and |x| != |y|} 

What is the best way to approach this question? At the moment I'm just using intuition to solve questions like these but are there useful techniques? i.e. could you think of what the PDA for this language would look like and then derive the grammer from that? Is there a method for finding a grammer G = A and B using grammars A and B?

I'm struggling to see how to solve this so any help would be much appreciated.

Thanks.

Answer 1

Using intuition is a valuable technique. As you solve more such problems, your intuitions sharpen, so it gets easier.

There's no formal technique to convert a description of a language into a CFG (unless the description is something which maps onto CFGs, of course, like a set of production rules). It is not, in general, decidable whether a language is context-free (although CFGs must conform to a lot of constraints, so it is often possible to prove that a language is not CFG, even semi-mechanically using counting arguments.) And it is not even necessarily the case that the intersection of two context-free languages is context-free, so there is no procedure which can take two context-free languages and generate a CFG for their conjunction.

However, the union of two context-free languages is context-free, and the CFG can be produced mechanically from the CFGs of the two languages. So there is some possibility to break problems down into pieces.

In the case of this particular problem, I suggest a simple heuristic, which will often work for the sort of questions you get in formal languages classes: Try to base the problem on simpler problems whose answer you know.

As above, the union of two CFLs is context free. So is the concatenation, defined as:

L₁·L₂ = {xy | x ∈ L₁ ∧ y ∈ L₂}

Here's two approaches, both based on being able to construct a similar language where |x| = |y|. Any string where |x| ≠ |y| must have more characters either on the right-hand side or on the left-hand side. Depending on your inclination, you could add these extra characters in the middle (on one or the other side of the separator) or on one of the ends. Both of these approaches involving using a union; one of them is a concatenation and the other an embedding.

Good luck.