CFG for a = b and c = d (length)

Question

I know how to construct the context-free grammars for strings that have same counts of a and b, or have the same counts of c and d:

S → ε             S → ε
S → SASBS         S → SCSDS
S → SBSAS         S → SDSCS
A → a             C → c
B → b             D → d

But, I don't know how to create a grammar for strings where the counts of a and b are the same, and the counts of c and d are the same. My attempts fail for strings like cadbdabc where the pairings are between each other (ex: c, <a>, d, <b>). So, I would appreciate if someone could help out on this.

Answer 1

The language you are trying to recognise is not context-free, so you're not going to be able to construct a context-free grammar for it.

To see that, remember that the language aⁿc^mbⁿd^m is not context-free. (You can easily prove that using the pumping lemma; in fact, it's one of the classic examples. Take a string where both m and n are greater than the pumping constant p; any substring uvx whose length is no greater than p can contain at most two different symbols with two different repetition counts; so replacing u and x with the empty string -- pumping 0 repetitions -- must make one of the equalities false.)

Now, let L be your language, and consider the intersection L ∩ a*c*b*d*. The intersection of a context-free language and a regular language is guaranteed to be context-free, and a*c*b*d* is obviously regular. So if L were context-free, then L ∩ a*c*b*d* would be context-free. But L ∩ a*c*b*d* is precisely the language aⁿc^mbⁿd^m, which is not context-free; a contradiction. Thus, L cannot be context-free.