# Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.

The professor hasn't given the correction.

I have seen similar questions but the condition is different, I can't find the grammar. Is it possible to prove that it is not context free?

EDIT: taking inspiration from other slightly similar solved question, here's my solution, but I think it could be factorized/improved

S -> S1 | S2
// S1 is the case where I will try to pair a with c (i.e when there more c than d), S2 is the case where I will try to pair d with b (i.e when there are more b than a)
S1 -> XY
X -> aXc | Z // for each a generate a c
Z -> aZb | epsilon // for each a generate a b
Y -> cYd | epsilon // for each d generate c
// since all the b's have been generated along with a's, i did not find a way to pair d's with b's
S2 -> UV
U -> aUb | epsilon
V -> bVd | W
W -> cWd | epislon

• You can see the language is context-free because it is quite easy to construct a PDA for it (just use the stack as a counter; when reading $a$'s and $d$'s, increase the counter; when reading $b$'s and $c$'s, decrease it). Although not a popular method, you could then always use the PDA -> CFG construction given by the equivalence theorem. – dkaeae Mar 7 '19 at 9:46
• i have just learned about pda after reading your comment. as such i dont think the teacher presumed knowledge of that concept to solve the problem. i think i have found a solution however, editing my post – truvaking Mar 7 '19 at 9:51
• @dkaeae What is a PDA? – justinpc Mar 7 '19 at 10:20
• pushdown automata – truvaking Mar 7 '19 at 10:31
• @truvaking. <enter pedant mode> automaton <leave pedant mode> – Rick Decker Mar 7 '19 at 13:22

Note if $$n, we can write $$a^nb^mc^qd^p$$ as $$a^nb^nb^xc^qd^{x+q}$$ where $$n,x,q$$ are independent of each other. Otherwise, we can write $$a^nb^mc^qd^p$$ as $$a^{m+y}b^mc^yc^pd^p$$ where $$m,y,p$$ are independent of each other.
So the grammar can be $$S\rightarrow S_1S_2\mid S_3S_4$$, where $$S_1$$ generates $$a^nb^n$$, $$S_2$$ generates $$b^xc^qd^{x+q}$$, $$S_3$$ generates $$a^{m+y}b^mc^y$$, and $$S_4$$ generates $$c^pd^p$$. They are all easy to construct.