Question

I'm studying context free grammar and I'm curious what the arrow with the star and the arrow without the star mean in parts f and g where:

  • f is false.
  • g is true.

enter image description here

Was it helpful?

Solution

"x ⇒ y" means that y can be derived from x in exactly one application of some production of the grammar. Putting an asterisk over the ⇒ means that y is derived from x via zero or more (but finitely many!) applications of some sequence of productions.

OTHER TIPS

See http://en.wikipedia.org/wiki/Context-free_grammar#Repetitive_rule_application for an explanation.

That is to say, if u star-arrow v, there is some series of applications of rules that goes from u to v.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top