2
$\begingroup$

I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages.

What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?

$\endgroup$
  • $\begingroup$ This is in the context of grammars, right? $\endgroup$ – Raphael Dec 2 '15 at 12:14
  • $\begingroup$ I've placed the * where it belongs. Look at the source to see how. $\endgroup$ – Rick Decker Dec 2 '15 at 14:40
  • $\begingroup$ @RickDecker I've certainly seen it in the other place, too. $\endgroup$ – Raphael Dec 2 '15 at 15:00
5
$\begingroup$

It's either the transitive closure or reflexive-transitive closure of $\rightarrow$. That is, $A\rightarrow B$ means that you get from $A$ to $B$ in exactly one step; $A\rightarrow^*B$ means either you get to $B$ in one or more steps (transitive closure) or in zero or more steps (reflexive-transitive closure).

$\endgroup$
  • $\begingroup$ * is reflexive, + is only transitive. $\endgroup$ – PleaseHelp Dec 2 '15 at 12:22
  • 2
    $\begingroup$ @calmyoursenses I would encourage everyone to use the notation that way but I can't guarantee that everybody actually does. $\endgroup$ – David Richerby Dec 2 '15 at 13:30

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.