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, 2019 at 18:52
1 Answer
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.