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
  • $\begingroup$ 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. $\endgroup$ – dkaeae Mar 7 '19 at 9:46
  • $\begingroup$ 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 $\endgroup$ – truvaking Mar 7 '19 at 9:51
  • $\begingroup$ @dkaeae What is a PDA? $\endgroup$ – justinpc Mar 7 '19 at 10:20
  • $\begingroup$ pushdown automata $\endgroup$ – truvaking Mar 7 '19 at 10:31
  • $\begingroup$ @truvaking. <enter pedant mode> automaton <leave pedant mode> $\endgroup$ – Rick Decker Mar 7 '19 at 13:22

Note if $n<m$, 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.