I have a language like this and will need to write the Context-free grammar for it.
$$\{a^n b^m c^k\; : \;k = |n-m|,\; m, n, k \geq 0\}$$
What I am confused is do I need to simplify the condition of k = |n-m| to solve or it just means the length
[Math] Find the CFG for $a^n b^m c^k$
context-free-grammar
Best Answer
Consider breaking it into the two cases $n\geq m$, $k=n-m$ and $m\gt n$, $k=m-n$; if you can find grammars for these two cases then you can just union them together to get your final CFG. As a further hint, note that in each case you can eliminate the larger of $m$ and $n$ in favor of $k$ and the smaller one; for instance, in the case $n\geq m$ then $n=m+k$ and so that 'half' of the grammar can be written as $a^{m+k}b^mc^k$ - or, more suggestively, $a^ka^mb^mc^k$. Can you see where to go from here?