context-free-grammarcontext-free-language

What's the Context-Free grammar of this language :L= {a^n b^m c^p d^q / m+n=p+q where n,m,p,q >=0 }


I was trying to find the context-free grammar of
L= {a^n b^m c^p d^q / m+n=p+q where n,m,p,q >=0 } but I'm stuck. This is what I did so far:

S -> X S Y | epsilon
X -> a|b
Y -> c|d

but I figured out that it doesn't respect the order, for example bacd is accepted but it shouldn't:

X S Y -> XX S YY -> ba S cd -> bacd

Solution

  • We can "force" the order using the following "trick":

      S -> aSd |  X | Y
      X -> bXd | Z
      Y -> aYc | Z
      Z -> bZc | epsilon
    

    Basically, we allow S to only derive a's and d's (the "outer" part of a fully derived word). Then, we allow S to derive either X or Y, each of them representing a change: we start to write b's instead of a's or start using c's instead of d's (this is the second-innermost part of a fully derived word), and finally Z allows only b's and c's (which is the innermost part of a fully derived word)