CFG for the language $L = \{(a^n)(b^m)(c^k) \mid k = |n – m|, n,m,k \geqslant 0\}$

789 Views Asked by At

These two are among given solution. I find (A) is correct, but the answer shows (D). Please answer which one of this is correct and why/explain.

(A) $S → S_1S_3$, $S_1 → aS_1c + S_2+ λ$, $S_2 → aS_2b+λ$, $S_3 → aS_3b+ S_4 + λ$, $S_4 → bS_4c+λ$

(D) $S → S_1 + S_3$, $S_1→ aS_1c+S_2 + λ$, $S_2 → aS_2b + λ$, $S_3 → a S_3b + S_4 + λ$, $S_4 → bS_4c + λ$

1

There are 1 best solutions below

0
On

Grammar (A) generates the word $acab$ which is not in $L$. $$ S \to S_1S_3 \to aS_1cS_3 \to acS_3 \to acaS_3b \to acab $$