1
$\begingroup$

enter image description here

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.