Changes

:Any item which appears on the left-hand side of a transformation rule is non-terminal since it can be replaced by something else; apart from the starting point, all other non-terminals must also appear somewhere on the right-hand side of transformation rule.

:Any item which appears on the left-hand side of a transformation rule is non-terminal since it can be replaced by something else; apart from the starting point, all other non-terminals must also appear somewhere on the right-hand side of transformation rule.

:An item which appears only on the right-hand side of a transformation rule is a terminal item, since it can not be transformed further.

:An item which appears only on the right-hand side of a transformation rule is a terminal item, since it can not be transformed further.

 

Many different classes of generative grammars can be obtained by varying the constraints which govern what sort of rules can be used; the Chomsky hierarchy, detailed below, is obtained by modifying the constraints.

:Linguists have developed various classes of grammars by using constraints to govern what sort of rules can be used for any particular grammar.

===Changing the rules===

===Changing the rules===

An relatively small change to even a single rule can make a large change in the language which can be generated. For example, change the first rule in the simple example to read:

An relatively small change to even a single rule can make a large change in the language which can be generated. For example, change the first rule in the simple example to read:

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

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

In addition to the shorter sentences already discussed, this could generate a sentence such as: "A dog saw a girl and the dog chased the girl". The total number of grammatically-correct sentences which can be generated by this modified grammar is now 11,772 (108 + 108*108).

This means that a ''Sentence'' is either a ''NounPhrase'' followed by a ''VerbPhrase'' or a ''NounPhrase'' followed by a ''VerbPhrase'' followed by '''and''' followed by a ''NounPhrase'' followed by a ''VerbPhrase''. In addition to the shorter sentences already discussed, this could also generate a sentence such as: "A dog saw a girl and the dog chased the girl". The total number of grammatically-correct sentences which can be generated by this modified grammar is now 11,772 (108 + 108*108), though some of these may not be very meaingful.

===Towards infinity===

===Towards infinity===

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

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

The distinction between left- and right-recursive becomes important when trying to parse/analyse a sentence; some types of parser work best with left-recursive grammars, while other types work best with right-recursive grammars. This distinction is particularly relevant in connection with [[compiler|compiling or translating]] a program written in some high-level programming language so that it can be used on a computer.

The distinction between left- and right-recursive becomes important when trying to parse/analyse a sentence; some types of parser work best with left-recursive grammars, while other types work best with right-recursive grammars. This distinction is particularly relevant in connection with [[compiler|compiling or translating]] a program written in some high-level [[programming language]] so that it can be used on a [[computer]].

==Chomsky hierarchy==

==Chomsky hierarchy==