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$.
Best Answer
Why don't you use the following easy grammar, where S is the starting variable?
S $\rightarrow$ BS | $\varepsilon$
B $\rightarrow$ a | b | c
Edit for your update:
You want to prove that $L_2$ is context free.
However, as Yuval said $L_3 = \{a^mb^nc^k \mid m,n,k \in \mathbb{N}\}$ is regular.
Now, since $\Sigma^*$ is regular and $\Sigma^*$\ $L_3$ is your wanted language, we know that $L_2$ is regular since regular languages are closed under difference, which implies that $L_2$ context free.