# Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$S \to aSaS \mid b$$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, but it's not very helpful tho.

• Hint: what about $S \to (S)S \mid b$? – Raphael Dec 7 '15 at 21:38
• I tried replacing aS or S in many ways but i don't know the universal solution for multiple recursion in a single rule. What do these brackets mean? – user43385 Dec 7 '15 at 22:23
• @Raphael yes! coding binary trees. – Hendrik Jan Dec 8 '15 at 2:27
• "i don't know the universal solution for multiple recursion in a single rule" -- There is no "universal solution". In fact, I don't know what you even mean by that. You should heed D.W.'s answer; I've said as much as I'm going to with my hint (in which the parentheses are just terminal symbols). – Raphael Dec 8 '15 at 12:43

It's no wonder that you're having trouble with this; it's nasty. So as not to spoil the suspense, $L(G)$ is

The set of all $w\in\{a, b\}^*$ such that $w = a^{i_1}b\,a^{i_2}b\dotsm a^{i_n}b$ with $i_k\ge 1$ for all $1\le k\le n$ and $$\sum_{k=1}^n i_k=2n-2$$

The proof is basically int two parts. First it's clear that any word generated by the grammar must end in $b$ and that no two $b$'s can be adjacent, so any word in $L(G)$ must have the form noted above.

To show the sum part, let's count the number of $S$'s, $a$'s and $b$'s in any sentential form that results from starting with $S$ and using either of the two productions of the grammar. Let $(s,a,b)$ represent these counts. We have

1. The production $S\rightarrow aSaS$ will change $(s,a,b)$ to $(s+1, a+2, b)$, since we're adding two new $a$'s and one more $S$.
2. The production $S\rightarrow b$ will change $(s,a,b)$ to $(s-1, a, b+1)$.
3. We start with the count $(1,0,0)$.
4. Note that production (1) followed by production (2) yields the same counts as we would have by using the productions in the opposite order, (2), (1). This observation isn't critical, but it means that we have a particularly pretty form when we apply the productions to the count tuples.
5. A count $(s,a,b)$ corresponds to a word in $L(G)$ only if $s=0$.

Starting with $(1,0,0)$ we now take D.W.'s tack and look at some small examples. Considering the counts with $s=0$, we find $(0,0,1), (0,2,2), (0,4,3), (0,6,4), (0, 8, 5)$ and so we guess that all the words in the language must have counts of the form $(0, 2n-2, n)$. We're done, right? Well, not quite. We need to show that (1) our guess about the counts was correct, and (2) that we actually can get any sequence of $i_k$'s satisfying these conditions. Fortunately, both pieces are more or less easy to show by induction, though the second one is somewhat messy.

By the way, we can also show that any string in $L(G)$ must have length $3n-2$ and that there are $\binom{n}{2}$ such strings.

One standard way to find $L(G)$ is via "guess-and-check". In other words:

1. Generate many example words using the grammar. You might generate all words of length $\le k$, for some small $k$ (e.g., $k=5$ or $k=10$). Write down all of those words so you can stare at them.

2. Look for a pattern in this list of words. Make a guess at what $L(G)$ might be, based on the pattern.

3. Finally, prove your guess correct using the techniques described at How to show that L = L(G)?.

This can unfortunately get pretty tedious, and requires you to make a guess at the pattern.

In your case, the first few words are abab, aababab, abaabab, etc. Keep going: generate a longer list. Then, see if you can find any pattern.

• I try to find this pattern for 2 days and now i'm about to cry. Is it possible to find pattern with some algorithm? I want to create appliacation which finds them, but now it works only with simple recursions. – user43385 Dec 7 '15 at 20:55
• @user43385 Since there is no formal definition of "pattern", no, there is no algorithm. It's a creative task. – Raphael Dec 7 '15 at 21:38
• >no formal definition of "pattern" i just mean L(G) – user43385 Dec 7 '15 at 21:52
• @user43385 I know, but how do you want to write it down? English? Set-constructor notation? Grammar? Automaton? Logical formulae? The list is long... – Raphael Dec 8 '15 at 12:41