Frequently in cs blogs and books I see this notation, =>* and =>+ but I am not sure how it is being applied in a production rule and it's significance. What exactly does it represent, and can you show an example of it being applied.

  • $\begingroup$ Have you found some textbooks that explain those notations? I am sure some of them do. $\endgroup$ – John L. Apr 22 '19 at 18:52

In most CS contexts, including this one, $X^*$ means any number of $X$'s, including zero, and $X^+$ means one or more $X$'s.

So $A\Rightarrow^* B$ just means that $A$ gets to $B$ by some number of steps and, if that number is zero, then $A=B$. More formally, it means that there is some number $\ell\geq 1$ and objects $C_1, \dots, C_\ell$ such that $A=C_1$, $B=C_\ell$ and $C_i\Rightarrow C_{i+1}$ for each $i\in\{1, \dots, \ell-1\}$. $A\Rightarrow^+ B$ means the same thing except with $\ell\geq 2$.

So, for example, given the grammar $$S\to aS\mid b\,,$$ we have $$S\Rightarrow aS\Rightarrow aaS\Rightarrow aab\,,$$ so we can write $S\Rightarrow^*aab$. In this case, $\ell=4$, $C_1=S$, $C_2=aS$, $C_3=aaS$ and $C_4=aab$. Since $\ell\geq 2$, we can also say $S\Rightarrow^+ aab$. We can also write $S\Rightarrow^*S$, which is $\ell=1$, $C_1=S$; but we can't write $S\Rightarrow^+S$, because any positive number of productions from $S$ will give a string with at least one terminal symbol in it.

| cite | improve this answer | |

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.