Infinite CFLs and Another Pumping Theorem

Intuitive reasoning behind the pumping theorem for CFLs

Now that we know how to determine if a context-free grammar generates an infinite language, let’s look a little closer at such languages. Suppose $A$ is a recursive variable in some CFG. Beginning with the start variable until the time $A$ first appears in a working derivation, symbols will have accumulated around $A$. Look at the CFG below and the following derivation:

We’ll denote the $aa$ prefix by $u$ and the last $a$ by $z$ so we have $A\Rightarrow ^* uAz$ so far. Now we continue substituting until $A$ is repeated:

We have picked up $v=b$ and $y=ab$ around $A$, giving us:

We can make the same choices we made previously between the occurrences of $A$ to arrive at $A$ again, giving us:

In general, with any recursive variable, we can derive this:

Eventually, we must terminate. We denote our terminating choices with $A\Rightarrow ^* x$, finally arriving at $S\Rightarrow ^* uv^nxy^nz$. In this instance, we can use the rule $A\Rightarrow \lambda$ and $n=2$ ending with the string $uv^2xy^2z= aabbababa$, where $x=\lambda$. We could also go right to the terminal rules, avoiding generating $v$ and $y$ in the first place, by letting $n=0$, which is the derivation:

Since $B$ ...