Menu
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:
382
In every context-free grammar, one of the non-terminal symbols is designated as the start symbol of the grammar. The start symbol is often, though not always, denoted by S. When the grammar is used to generate strings in a language, the idea is to start with a string consisting of nothing but the start symbol.
A context free grammar has 4 components: – A set of tokens, known as terminal symbols. – A set of nonterminals. nonterminal, called the left side of the production, an arrow, and a sequence of tokens and/or nonterminals, called the right side of the production.
Context-free grammars (CFGs) are used to describe context-free languages. A context-free grammar is a set of recursive rules used to generate patterns of strings. A context-free grammar can describe all regular languages and more, but they cannot describe all possible languages.
"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. Follow this answer to receive notifications.
"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.
70
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.
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
