what are these arrow operators in context free grammar?
-
26-10-2019 - |
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.
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