Below we have a BNF grammar defined by grammar G(N, T, P, S), N={S, C}, T = {a, b, c} and set of productions rules are:
S -> S a S b S | S b S a S | C S | S C | Epsilon
C -> c C | Epsilon
Epsilon - empty word
| - or
Describe this language. I have no idea how to do this. I understand easy examples, but this is really difficult. Please, help me. :)
I’ll go through this in some detail rather than give a hint, since I think that seeing the kind of reasoning that I use may be helpful in thinking about other problems of this kind.
Let $L$ be the language generated by this grammar. For each $w\in L$ let $|w|_a$ be the number of $a$s in $w$ and $|w|_b$ the number of $b$s in $w$. First note that $a$s and $b$s can only be generated by the productions $S\to SaSbS$ and $S\to SbSaS$, so every $w\in L$ must satisfy the condition $|w|_a=|w|_b$: each $a$ generated for $w$ comes with a paired $b$ in $w$. For each $w\in L$ let $n(w)=|w|_a=|w|_b$.
Next, observe that the strings derivable from $C$ are precisely the strings of the form $c^n$ for $n\ge 0$; these are all of the words over the alphabet $\{a,b,c\}$ that have no $a$s or $b$s, i.e., the $w\in L$ such that $n(w)=0$.
Now consider a derivation of some $w\in L$ such that $n(w)=m>0$. The productions $S\to SaSbS$ and $S\to SbSaS$ must be used a total of $m$ times, since each instance produces one $a$ and one $b$. Find the last instance of one of these productions in the derivation of $w$. Note that you can rearrange the derivation, if necessary, to ensure that any applications of the production $S\to\epsilon$ occur after this instance. Thus, at this point you have a string that contains $m$ each of $a$s and $b$s, $3m$ instances of $S$, and some unknown numbers of $C$s and $c$s. Moreover, there is at least one $S$ between any instance of $a$ or $b$ and any other instance of $a$ or $b$. Try to convince yourself that if we throw away all of the symbols that are not $a$ or $b$, we can have any string of $m$ $a$s and $m$ $b$s in any order. (If you’re ambitious, you can try to prove this by induction on $m$.)
Each of the remaining instances of $S$ must produce $CS$, $SC$, or $\epsilon$, so in fact each produces some string of the form $c^n$ with $n\ge 0$. Thus, that $m$ $a$s and $m$ $b$s can have any numbers of $c$s before, between, and after them. This shows that copper.hat’s suspicion is correct:
$$L=\big\{w\in\{a,b,c\}^*:|w|_a=|w|_b\big\}\;.$$