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