Just to make it clear. (since my book doesn't mention anything like this)

Suppose we have a context free grammar $G=(V,T,P,S)$. where $T=\{a,b\}$ (The other sets doesn't really matter).

Since $\Rightarrow^*$ is the reflexive transitive closure of the relation $\Rightarrow$ on the set $(V\cup T)^*$, I see no problem in writing a thing like $ab \Rightarrow^* ab$ (where $ab\in T^*$ and there are no variables on the left hand side of the arrow) since the $\Rightarrow^*$ relation is reflexive.

Now I want to ask wether it common to write a thing like $ab \Rightarrow^* ab$?

By definition I see no problem.



1 Answer 1


There is absolutely no problem writing $ab \Rightarrow^* ab$. It definitely happens in proofs.

  • $\begingroup$ Thanks a lot, Indeed I have encountered this in my proof and it is a lot easier to use this notation especially if there are several cases to consider (for instance $X$ may be a terminal word or a variable that derives a terminal word). $\endgroup$
    – MathNerd
    Commented Jan 4, 2016 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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