SkipCaptcha
265
edits
Changes
add section: Formal grammar
}}</ref>
}}</ref>
==Chomsky hierarchy==
==Formal grammar==
'''Note''': this section is, 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, 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.
A formal generative grammar has four components (see slide 19 of this
A formal generative grammar has four components (see slide 19 of this lecture
<ref>{{cite web
<ref>{{cite web
| url = http://adammikeal.org/courses/compute/Chomsky%20Presentation.pdf
| url = http://adammikeal.org/courses/compute/Chomsky%20Presentation.pdf
| title = The Chomsky Hierarchy
| title = The Chomsky Hierarchy
| accessdate = 2012-04-06
| accessdate = 2012-04-06
}}</ref> lecture):
}}</ref>
):
# a finite number of non-terminal concepts (e.g. ''VerbPhrase'' in the example, or anything else in ''italics''),
# a finite number of non-terminal concepts (e.g. ''VerbPhrase'' in the example, or anything else in ''italics''),
# a finite number of terminals (e.g. '''the''', '''girl''' in the example, or anything else in '''bold-face''').
# a finite number of terminals (e.g. '''the''', '''girl''' in the example, or anything else in '''bold-face''').
# a finite set of rules for transforming non-terminal items (e.g. the example has 6 rules).
# a finite set of rules for transforming non-terminal items (e.g. the example has 6 rules).
# a starting point (e.g. ''Sentence'' in the example).
# a single starting point (e.g. ''Sentence'' in the example).
Notes:
: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.
==Chomsky hierarchy==
Chomsky defined 4 grammar levels; level 3 is a subset of level 2, which is a subset of level 1, which is a subset of level 0. The higher the level number, the simpler the generated language is, while the lower the level number the more difficult it is to parse a sentence in that language.
Chomsky defined 4 grammar levels; level 3 is a subset of level 2, which is a subset of level 1, which is a subset of level 0. The higher the level number, the simpler the generated language is, while the lower the level number the more difficult it is to parse a sentence in that language.
<ref>{{cite web
<ref>{{cite web