SkipCaptcha
265
edits
Changes
→Chomsky hierarchy: outline of a formal grammar
==Chomsky hierarchy==
==Chomsky hierarchy==
'''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 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.
A formal generative grammar has four components (see slide 19 of this
<ref>{{cite web
| url = http://adammikeal.org/courses/compute/Chomsky%20Presentation.pdf
| title = The Chomsky Hierarchy
| accessdate = 2012-04-06
}}</ref> lecture):
# 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 set of rules for transforming non-terminal items (e.g. the example has 6 rules).
# a starting point (e.g. ''Sentence'' in the example).
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.
| accessdate = 2012-04-07
| accessdate = 2012-04-07
}}</ref>
}}</ref>
===Level 0===
===Level 0===