SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 95:
Line 95: − + Line 112:
Line 112: + + + + + + + + + + + + + + + + + Line 120:
Line 137: −
variations on a formal grammar
==Formal grammar==
==Formal grammar==
'''Note''': this section and subsequent sections are, by necessity, somewhat more technical/formal than the earlier parts of this article. Make sure that you understand the 'Simple example' above before proceeding further, since references will be made to that example to help explain the technicalities.
'''Note''': this section and subsequent sections are, by necessity, slightly more technical/formal than the earlier parts of this article. Make sure that you understand the 'Simple example' above before proceeding further, since references will be made to that example to help explain the technicalities. An attempt has been made to avoid formal linguistic abbreviations and unexplained jargon.
A formal generative grammar has four components (see slide 19 of this lecture
A formal generative grammar has four components (see slide 19 of this lecture
: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.
===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:
''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).
===Towards infinity===
A significantly different rule change can have an astounding effect. Consider changing the first rule to read:
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'', ''NounPhrase'' ''VerbPhrase'' '''and''' ''Sentence''
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 generate exactly the same sentences.
''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.
==Chomsky hierarchy==
==Chomsky hierarchy==
| accessdate = 2012-04-07
| accessdate = 2012-04-07
}}</ref>
}}</ref>
===Level 0===
===Level 0===