The Language generated by the grammar

Question

Describe the language generated by the grammar G with such production rules:

$$\begin{align*} S&\to a\mid bS\mid cSS\end{align*}$$

After thinking a bit we can get the next result (though it is not very formal): $$\begin{align*} S&\to a\mid cSS\mid b^nc^m(S)^{m + 1} \end{align*}$$ for some $$n, m \in \mathbb{N} $$ For every S n and m can be different. I cannot understand what is this language.

Answer 1

Let $L$ be the language generated by $G$. The only terminal production is $S\to a$, so every word in $L$ must end in $a$. Moreover, every production generates a terminal symbol, so every $b$ in a word of $L$ must be followed by at least one more symbol, and every $c$ in a word of $L$ must be followed by at least two more symbols.

It’s easy to see that the words produced by derivations that do not use the production $S\to cSS$ are precisely the words of the form $b^na$ for $n\ge 0$: $n$ is the number of times the production $S\to bS$ is used before the derivation is terminated by the production $S\to a$. I’ll call words of $L$ of this form basic words.

Now suppose that a derivation uses the production $S\to cSS$ exactly once, after using $S\to bS$ $n_1$ times. At that point we have the derivation

$$S\Rightarrow^{n_1}b^{n_1}S\Rightarrow b^{n_1}cSS\,.$$

Since the derivation uses $S\to cSS$ only once, each of those last two $S$s must produce a basic word, so we’ll end up generating a word $b^{n_1}cb^{n_2}ab^{n_3}a$ for some $n_1,n_2,n_3\ge 0$.

What happens if the derivation uses $S\to cSS$ twice? Depending on whether the second application of $S\to cSS$ derives from the first or the second $S$ in $b^{n_1}cSS$, we can get either $b^{n_1}cb^{n_2}cb^{n_3}ab^{n_4}ab^{n_5}a$ or $b^{n_1}cb^{n_2}ab^{n_3}cb^{n_4}ab^{n_5}a$. If we use $A$ to stand for any basic word and $C$ to stand for any word of the form $b^nc$ with $n\ge 0$, we can represent these as $CCAAA$ and $CACAA$, respectively. In these terms the words generated by derivations that use $S\to cSS$ once are the words of the form $CAA$.

At this point it’s not hard to see that a derivation that uses $S\to cSS$ three times will produce a word of one of the following forms:

$$\begin{align*} &CCCAAAA,CCACAAA,CCAACAA,\\ &CACCAAA,CACACAA \end{align*}$$

These are the forms that can be obtained by replacing one $A$ in $CCAAA$ or $CACAA$ with $CAA$; this corresponds to replacing one use of the production $S\to bS$ with one use of the production $S\to cSS$.

If we think of each word of the form $C$ as a left parenthesis and each word of the form $A$ as a right parenthesis, it appears so far that we are generating strings that consist of a well-formed parenthesis string followed by one extra right parenthesis. Try to prove by induction on the number of uses of the production $S\to cSS$ that this is precisely what we get; that will give you a complete description of $L$.

Answer 2

Let f:$$ \forall w \space \in \space \{a, b, c\}^*: f(w) = |w|_c - |w|_a$$ Then G is generating L, where: $$ L = \{w \in \{a, b, c\}^*: \forall u_1: w = u_1u_2 \space(u_2 \ne e)\space f(u_1) \ge 0, \space w[-1] = a,\space f(w) = -1\}.$$

Answer 3

Here is a possible interpretation for the strings in your language.

Build (rooted, ordered) trees, where nodes are labelled with $a,b,c$. Nodes with $c$ always have two children, those with $b$ have a single child, and $a$ have no children (they are leafs). Example below. (Technically that is called a ranked alphabet.)

Now the strings represent the pre-order traversal for these trees. Since the alphabet is ranked, in fact the pre-order traversal determines the tree itself. The tree in the picture represents $ccbacbbabacbacbbaa$.