How to describe this Context Free Grammar?

Question

I've been having a really difficult time in describing the following Context Free Grammar

S → SS | T
T → aTb|ab

I understand that it must start with an a and end in a b. But other than that, what kind of stuff can go in between there? How do I describe that?

Answer 1

First consider what terminal strings you can derive from a single $T$, as if $T$ were the initial symbol, and you had only the productions $T\to aTb\mid ab$. You can apply the production $T\to aTb$ $n$ times for any $n\ge 0$; that gives you $a^nTb^n$. Eventually, though, you must apply $T\to ab$, and at that point you have $a^{n+1}b^{n+1}$. In other words, you can get everything of the form $a^nb^n$ with $n\in\Bbb Z^+$.

$S$ cannot directly produce any terminal string, so in any terminal derivation every $S$ must eventually be changed to a $T$. The production $S\to SS$ means that you can generate $S^k$ for any $k\in\Bbb Z^+$, but eventually you’re going to have to turn each $S$ to $T$. It doesn’t matter whether you do that all at once to get $T^k$ and then apply the productions $T\to aTb$ and $T\to ab$, or whether you work with some of the $T$s before you turn every $S$ to a $T$: the derivations from the individual $T$s are independent of one another.

Thus, you can get precisely the words of the form

$$a^{n_1}b^{n_1}a^{n_2}b^{n_2}\ldots a^{n_k}b^{n_k}\;,\tag{1}$$

where $k\in\Bbb Z^+$ is the number of copies of $S$ that were turned into $T$s, and the $i$-th copy of $T$ generated $a^{n_i}b^{n_i}$ for some $n_i\in\Bbb Z^+$.

In any derivation of the word $(1)$

• the production $S\to SS$ was applied $k-1$ times;
• the production $S\to T$ was applied $k$ times;
• the production $T\to aTb$ was applied $$(n_1-1)+(n_2-1)+\ldots+(n_k-1)=\left(\sum_{i=1}^kn_i\right)-k$$ times; and
• the production $T\to ab$ was applied $k$ times.

However, there is a fair bit of freedom in the order in which these productions can be applies.