Changes

This can generate a potentially infinite number of sentences (any number of these five-word sentences linked by '''and'''). This is an example of what is known as a [[Recursion|recursive]] definition, whereby a ''Sentence'' is partially defined in terms of itself. In such a recursive rule there must be at least one transformation option which does not involve ''Sentence'', otherwise the transformation could never stop.

This can generate a potentially infinite number of sentences (any number of these five-word sentences linked by '''and'''). This is an example of what is known as a [[Recursion|recursive]] definition, whereby a ''Sentence'' is partially defined in terms of itself. In such a recursive rule there must be at least one transformation option which does not involve ''Sentence'', otherwise the transformation could never stop.

The above change is known as right-recursive; a left-recursive formulation is also possible, and can in this example generate exactly the same sentences.

The above change is known as right-recursive; a left-recursive formulation is also possible, and can in this example generate exactly the same sentences. As shown below  under 'Context-free grammar', there are situations where the choice of left- or right-recursive formulations can change the meaning.  

  ''Sentence''  ->  ''NounPhrase'' ''VerbPhrase'', ''Sentence'' '''and''' ''NounPhrase'' ''VerbPhrase''  

  ''Sentence''  ->  ''NounPhrase'' ''VerbPhrase'', ''Sentence'' '''and''' ''NounPhrase'' ''VerbPhrase''