What language is generated by this grammar?

Question

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

$$\begin{align*} S&\to aSaS\mid bSbS\mid \epsilon\end{align*}$$

I've tried to find some specific properties of some of the generated words, but I've failed.

Answer 1

One specific property of the generated words is pretty obvious: each of them must have an even number of $a$s and an even number of $b$s. It’s clearly more complicated than that, though, because there’s no way to generate $abab$.

What is perhaps the easiest way to see what’s going on isn’t obvious. Let’s look at a slightly different grammar:

$$S\to (S)S\mid [S]S\mid\epsilon\,.\tag{1}$$

Every word generated by this grammar can be turned into one generated by your grammar simply by changing each parenthesis to an $a$ and each square bracket to a $b$, and each word that your grammar generates can be obtained from this one in that way. This means that if we can figure out what language this grammar generates, we can figure out the language generated by your grammar.

The productions $(1)$ say that the shortest non-empty words generated by $S$ are $()$ and $[\,]$. Moreover, if $S$ can generate $w$ and $v$, then $S$ can generate $(w)v$ and $[w]v$. (Note that either or both of $w$ and $v$ can be empty.) If you think about this for a bit, you should be able to convince yourself that the grammar generates precisely the well-formed (i.e., balanced) strings of parentheses and square brackets. That is, if you had a correctly parenthesized algebraic expression using ordinary parentheses and square brackets, and you erased everything except the parentheses and square brackets, you’d get something generated by this grammar, and everything generated by this grammar can be obtained in that way.

Now try to apply that insight to describe the language generated by your grammar.