The most obvious one that I found was, $S \rightarrow SSS | A | B | C$ $A \rightarrow Aa | \epsilon$ $B \rightarrow Bb | \epsilon$ $C \rightarrow Cc | \epsilon$
However, I realize this CFG is ambious because we can generate different parse trees for the same string due to the rule $S \rightarrow SSS$.
So I revised my language to avoid ambiguity as follows:
$S \rightarrow SABC | ASBC | ABSC | ABCS $ $A \rightarrow Aa | \epsilon$ $B \rightarrow Bb | \epsilon$ $C \rightarrow Cc | \epsilon$
where $S$ is the starting variable in both grammars.
I wonder if this CFG is correct? What I wasn't sure is the first rule $S$, it looks a bit redundant but I don't know how to fix it so that it can generate all strings over the alphabet $\Sigma = \{a, b, c\}$. Any idea?
Update
The question is motivated from this problem:
Show that the complement of the language $L = \{a^nb^mc^k, k = n + m\}$ is context-free.
Since I already found the CFG for the language $L_1 = \{a^nb^mc^k, k \neq n + m\}$, what I'm trying to do is finding the CFG for its complement which includes two parts:
- $L_1$
- $L_2$ = Any string over alphabet $\Sigma = \{a, b, c\}$ that is not in the form $a^mb^nc^k$.
So if I can find the CFG for 2, the union of these two languages is also CFG by adding an extra rule: $S \rightarrow S_1 | S_2$ where $S_1$ is starting variable of $L_1$, and $S_2$ is starting variable for $L_2$.