[Solved]: Figuring out the language of a non-linear CFG

Problem Detail: 

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.

Asked By : user43385

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50456

3.2K people like this

 Download Related Notes/Documents