# What Do These Symbols Mean in Repetitive Rule Application and How Are They Applied Practically?

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.

• Have you found some textbooks that explain those notations? I am sure some of them do. Apr 22, 2019 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.