1
$\begingroup$

Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar.

As stated here, when $\Rightarrow^*$ is used, it means derive in 0 or more steps and when $\Rightarrow^+$ is used, it means derive in 1 or more steps.

What I don't understand is what is the use or importance of $\Rightarrow^*$ operator?. It just replaces the head of the production with the head itself.
Is it that the $\Rightarrow^*$ operator is just there to define operators in some standard way or it actually differs in the way it is used as compared to $\Rightarrow^+$?

Also, while deriving strings, to skip some obivious steps(like replacing multiple non-terminals in a string with their respective terminals), should I use $\Rightarrow^*$ or $\Rightarrow^+$?

$\endgroup$
2
$\begingroup$

It is false that $\Rightarrow^*$ " just replaces the head of the production with the head itself". $A \Rightarrow^* B$ means that the sentential form $B$ can be obtained from the sentimental form $A$ by applying any number of productions (which might be $0$ or more than $0$).

For example if your grammar is $S \to a$, then all of the following are true $S \Rightarrow^* S$, $S \Rightarrow^* a$, and $S \Rightarrow^+ a$, while it is false that $S \Rightarrow^+ S$.

If you are deriving strings and applying at least one production per step then both $\Rightarrow^*$ and $\Rightarrow^+$ are correct. The latter is more specific since it implies the former (but not vice-versa).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ According to you, "the sentential form B can be obtained from the sentential form A by applying any number of productions (which might be 0 or more than 0)", so in case of applying no productions while deriving a new string, I infer it means that the new derived string will be same as before. So, if my inference is correct then, what is the significance of this reflexive property of $\Rightarrow^*$ operator? $\endgroup$ – Perspicacious Apr 27 at 9:45
  • 1
    $\begingroup$ $A \Rightarrow^* B$ is just a notation to mean that $B$ can be derived from $A$ in some way. You use it when you want to express that... Consider a sample grammar $G$ defined as follows $S \to A|B, \quad A \to Aa | a, \quad B \to AA$. The following statement would be true: $\forall$ sentential form $X$, there exist a sentence $y \in a^*$ such that $X \Rightarrow^* y$. But the following statement would be false: $\forall$ sentential form $X$, there exist a sentence $y \in a^*$ such that $X \Rightarrow^+ y$. $\endgroup$ – Steven Apr 27 at 11:29
  • $\begingroup$ ok, so, does it mean the operator $\Rightarrow^*$ is required (if that's the correct word) to have a more comprehensive definition of the symbols?? $\endgroup$ – Perspicacious Apr 27 at 11:57

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.