# Nonterminal Complexity of a context-free grammar

Suppose $$G$$ is a CFG.

$$G = (N, T, P, S)$$,

$$Var(G)$$ as the cardinality of $$N$$

$$Var(L)$$= min {$$Var(G)$$ | G is a context-free grammar and $$L(G) = L$$}.

I have a problem in understanding a part of proof of the following lemma.

lemma: Let $$i_{1} , i_2 , . . . , i_{2n}$$ be $$2n$$ pairwise different positive integers and $$L = \{ab^{i_1} \}^∗ \{ab^{i_2} \}^∗ . . . \{ab^{i_{2n}} \}^∗$$ . Then $$Var(L) = n$$.

proof:

First it show that, for any nonterminal $$A$$ different from $$S$$, there is a rule $$A → xAy$$ with $$xy \neq λ$$.

My problem is in the second part:

We only discuss the case $$x \neq λ$$; the case $$y \neq λ$$ can be handled analogously. Obviously, $$G$$ has to be reduced, i.e., there is a derivation $$S =⇒* uAv =⇒* uwv ∈ L(G).$$ Moreover, let $$x =⇒ x' ∈ T^*$$ and $$y =⇒* y' ∈ T^*$$ two terminating derivations. Then, for any n ≥ 0, we have a derivation $$S =⇒* u A v =⇒* u (x')^n A (y' )^n v =⇒* u (x')^n w (y' )^n v ∈ L(G) = L$$ If $$n ≥ 2m + 1$$, then x^n contains a subword $$ab^{i_j}a$$ for some $$j$$. Assume that there are $$i_k$$ , $$k \neq j$$, and a derivation $$A =⇒* x'' A y''$$ where $$x''$$ contains the subword $$ab^{i_k}a$$. Then we have the derivation $$S =⇒* uAv =⇒* u x'' A y'' v =⇒* u x'' (x' )^n A (y')^n y'' v =⇒* u x'' (x' )^n x'' A y'' (y')^n y'' v =⇒∗ u x'' (x' )^n x'' w y'' (y')^n y'' v = p ∈ L(G)$$ which generates a word containing a subword $$ab^{i_k}azab^{i_j}az'ab^{i_j}a$$ which is not in $$L$$. Thus a letter $$A$$ can only contribute to one $$ab^{i_j}$$ to the left. Analogously, $$A$$ can only contribute to one $$ab^{i_j'}$$ to the right....

I don't understand why does $$x^n$$ contains a subword $$ab^{i_j}a$$ for some $$j$$, and why the final subword is $$ab^{i_k}azab^{i_j}az'ab^{i_j}a$$ not $$ab^{i_k}azab^{i_j}az'ab^{i_k}a$$. I don't have enough intuition about this concept. I learned CFLs from Sipser's book and I know about complexity from the algorithm course. Do I need extra information? If I do please recommend books, courses,... to help me get deep into this paper. The paper is about "Operational complexity and right linear grammars" .