# substitution of same variable in context-free grammars

Above is a theorem coming from the book "Formal languages and automata" by Peter Linz concerning substitution of variables. Could someone explain why A and B have to be different variables?

• What do you mean by A and B are different variable? Please elaborate more. Jun 20 at 22:06

As you suspect probably, theorem 6.1 still holds even if $$A$$ and $$B$$ are the same variable. This can be seen by following the proof of the theorem, assuming $$B$$ is $$A$$.
So, it is not correct to say "it is necessary that $$A$$ and $$B$$ be different variables" so that the conclusion $$L(\widehat G) = L(G)$$ holds. The quoted text is from the text right after the proof of that theorem in that textbook.
However, when $$A$$ and $$B$$ are the same variable, the change from $$G$$ to $$\widehat G$$ is unlikely to be helpful to simplify a context-free grammar by any reasonable measure. In order to simplify a context-free grammar, we would most probably use theorem 6.1 in the case when $$A$$ and $$B$$ are different variables, if we want to use it at all.