что это за стрелки в контекстно-свободной грамматике?

Question

Я изучаю контекстную грамматику, и мне любопытно, что означает стрелка со звездой и стрелка без звезды в частях f и g, где:

• е ложно.
• г верно.

Answer 1

«x ⇒ y» означает, что y может быть получено из x точно в одном приложении некоторого производства грамматики. Помещение звездочки над ⇒ означает, что y получается из x через ноль или более (но конечное число!) Приложений некоторой последовательности произведений.

Answer 2

См. http://en.wikipedia.org/wiki/Context-free_grammar#Repetitive_rule_application для объяснения.

То есть, если u звезда-стрелка v, есть ряд применений правил, которые идут от u к v.