Context Free Grammar and some details

Question

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free).

S -> SBA | a
BA -> AB
aA -> aaB
B -> b

Answer 1

This grammar itself is of course context-sensitive, so in order to show that the language is nicer than that, you’ll have to figure out what the language actually is. Note that the only way to get rid of $S$ is to apply the production $S\to a$, which you can do after applying $S\to SBA$ $n$ times for any $n\ge 0$. At that point you have the string $a(BA)^n$. If $n=0$, this is the terminal string $a$. Suppose that $n>0$, so that you have $aBA(BA)^{n-1}$. If you apply $B\to b$, you will have no way to get rid of the $A$s, so the only production that can be usefully applied is $BA\to AB$; this results in the string $aAB(BA)^{n-1}$. Now you can get rid of one $A$ by applying $aA\to aaB$ to get $aaBB(BA)^{n-1}$.

If $n=1$ this is $aaBB$, and the only possible terminal derivation from here is to $aabb$. If $n>1$, it’s $aaBBBA(BA)^{n-2}$, and you can apply the same reasoning as before to see that the only useful derivation is to $aaABBB(BA)^{n-2}$ and thence to $a^3B^4(BA)^{n-2}$.

If you continue the analysis in this vein, you should find that the language has a rather simple description, and once you’ve discovered that, you can design a linear grammar for the language.

Added: We’ve seen that the only real freedom in a derivation using this grammar is the number $n$ of times that we apply $S\to SBA$ before applying $S\to a$ to get rid of the initial symbol $S$. After that there is some variation in the order in which we can apply productions, but there’s only possible terminal string. If $n=0$, this string is $a$. If $n=1$, it’s $aabb$. If $n>1$, we get to $a^3B^4(BA)^{n-2}$; if $n=2$, this is $a^3B^4$, which generates $a^3b^4$. If $n>2$, we pull out one copy of $BA$ to get $a^3B^4BA(BA)^{n-3}$, use $BA\to AB$ repeatedly to run the first $A$ to the left through the $5$ $B$’s that precede it, and get $a^3AB^5(BA)^{n-3}$. We can now get rid of that $A$ by applying $aA\to aaB$ to get $a^4B^6(BA)^{n-3}$. If $n=3$, $5$ applications of $B\to b$ turn it into $a^4b^6$.

In general, if we have $a^kB^\ell(BA)^m$ with $m>0$, the only derivation that can reach a terminal string is

$$a^kB^\ell(BA)^m=a^kB^\ell BA(BA)^{m-1}\Rightarrow^*a^kAB^{\ell+1}(BA)^{m-1}\Rightarrow a^{k+1}B^{\ell+2}(BA)^{m-1}\;.$$

Thus, every time we get rid of one $BA$, we add an $a$ to the block of $a$’s at the beginning of the string, and we add two $B$’s between them and the $BA$’s. If we start with $a(BA)^n$, this will happen $n$ times before we get rid of all of the non-terminal symbols, and we’ll end up with $a^{n+1}b^{2n}$. In other words the language generated by this grammar is $L=\{a^{n+1}b^{2n}:n\ge 0\}$.

Now recall that a linear grammar is a context-free grammar that has at most one non-terminal symbol on the righthand side of each of its productions. You should be able to design such a grammar for $L$ without too much trouble: you can do it with just one non-terminal symbol, $S$, and two productions, one of which is $S\to a$.