What's the Context-Free grammar of this language : $L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ [duplicate]

Question

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

$$ S \to X S Y | \lambda$$ $$X \to a|b$$ $$Y \to c|d $$ but I figured out that it doesn't respect the order.
My Question is different from this one because here $n, m, p or q$ can be equal to $0$ which is not the case in the other question where the answer use $a, d >0$.

Answer 1

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

• $S\rightarrow aSd \mid X \mid Y$
• $X\rightarrow bXd \mid Z$
• $Y \rightarrow aYc \mid Z$
• $Z \rightarrow bZc \mid \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)