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" .
