I'm studying Context free Grammar and I have a question to a specific Exercise:
Why is i. True? How is this possible?
$\begingroup$
$\endgroup$
-
$\begingroup$ By the way, it is CS.SE policy to post text as text, not as an image. Here, you only needed the grammar plus the (i) item. $\endgroup$ – chi Jun 23 '18 at 18:00
$\begingroup$
$\endgroup$
For every nonterminal $A$ it always holds that $A \Rightarrow^* A$. This is because $\Rightarrow^*$ is the reflexive transitive closure of $\Rightarrow$. In words, $A \Rightarrow^* \alpha$ is $\alpha$ can be obtained from $A$ by applying zero or more productions.
The similar notation $\Rightarrow^+$ is the transitive closure of $\Rightarrow$, and corresponds to one or more productions. In your grammar, it isn't the case that $T \Rightarrow^+ T$.
answered Jun 23 '18 at 17:51
