0
$\begingroup$

I'm trying to generate a grammar from this language:

L={a^i b^j c^k d^l :  i+j=k+l}

to be clear its a in the power of i and b in the power of j... and so on, so that i+j will equal k+l, I would love an explanation how to get to the solution as well, thank you!

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Start with $i+j=k+\ell$. If $i\ge \ell$, say $=\ell+m$, then also $k=j+m$ and we can write strings in the form $a^\ell a^m b^j c^j c^m d^\ell$. Those can be generated by a grammar, you can use the basic toolbox.

Similarly when $i\le \ell$.

$\endgroup$

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