snippetMinor
Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m
Viewed 0 times
suchthecreatelanguagegeneratethatgrammar
Problem
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
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 | epislonSolution
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.
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.
Context
StackExchange Computer Science Q#105266, answer score: 4
Revisions (0)
No revisions yet.