HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
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

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

Solution

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.

Context

StackExchange Computer Science Q#105266, answer score: 4

Revisions (0)

No revisions yet.