[Math] The context free grammar for language $L = \{a^nb^mc^k \mid k = |n – m|, n≥0,m≥0,k≥0\}$ is

Question

The context free grammar for language $L = \{a^nb^mc^k \mid k = |n – m|, n≥0,m≥0,k≥0\}$ is:

1. $S→S_1S_3, S_1→aS_1c |S_2|λ, S_2→aS_2b|λ, S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$
2. $S→S_1S_3, S_1→aS_1S_2c |λ, S_2→aS_2b|λ, S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$
3. $S→S_1|S_2, S_1→aS_1S_2c|λ, S_2→aS_2b|λ, S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$
4. $S→S_1|S_3, S_1→aS_1c |S_2|λ, S_2→aS_2b|λ, S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$

---

My attempt:

None of these with given options

$S_3\implies aS_3b\implies aS_4b \implies abS_4cb\implies abcb$

Best way to by make either $n=k+m$ or $m=k+n$

Seems typo's with option $(3)$ too.

Can you explain it, please?

It also CFG for the language $L = \{(a^n)(b^m)(c^k) \mid k = |n – m|, n,m,k \geqslant 0\}$ asked there, but need more explaination, please.

Is it option $(4)$ true?

Answer 1

Option (4) is correct as first part has #a = #b+#c and second part has #b = #a+#c, which is required for given language.

First part, for $n=k+m$ : $$S_1→aS_1c |S_2|λ, S_2→aS_2b|λ$$ Second part, for $m=k+n$ : $$S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$$

Thus, $n=k+m$ or $m=k+n$ : $$S→S_1|S_3, S_1→aS_1c |S_2|λ, S_2→aS_2b|λ, S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$$

Language of above grammar would be inherently ambiguous.