Block, SkipCaptcha, apieditor, Automoderated users, Bots, edit, ratelimit-exempt
59,161
edits
Changes
Jump to navigation
Jump to search
Line 1:
Line 1: − + Line 15:
Line 15: − + Line 97:
Line 97: − + − + Line 112:
Line 112: − + − :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. + Line 139:
Line 139: − + + + + Line 157:
Line 160: − + Line 216:
Line 219: + Line 251:
Line 255: − + − For both regular grammars and context-free grammars, the left-hand side of any rule is always a single non-terminal item, and any transformation is applied regardless of the context in which that non-terminal item appears.+ + + − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + − + +
→top: Spelling/Grammar Check, typos fixed: 1950's → 1950s
The '''Chomsky hierarchy''', sometimes known as the '''Chomsky-Schützenberger hierarchy''', is a hierarchy of formal grammatical systems for describing various classes of languages; the hierarchy can apply to both human and computer languages. This hierarchy was first published in 1956 by [[Noam Chomsky|Chomsky]].
The '''Chomsky hierarchy''', sometimes known as the '''Chomsky-Schützenberger hierarchy''', is a hierarchy of formal grammatical systems for describing various classes of languages; the hierarchy can apply to both human and computer languages. This hierarchy was first published in 1956 by the linguist [[Noam Chomsky|Chomsky]].
<ref>{{cite journal
<ref>{{cite journal
| title = Three models for the description of language
| title = Three models for the description of language
The basic idea of a '''generative grammar''' is to provide a set of rules which are capable of generating all possible grammatical sentences in some language; the rules must constrain the generation so that only grammatical sentences are generated. The rules can also be used in reverse to parse a sentence and check if it is grammatical.
The basic idea of a '''generative grammar''' is to provide a set of rules which are capable of generating all possible grammatical sentences in some language; the rules must constrain the generation so that only grammatical sentences are generated. The rules can also be used in reverse to parse a sentence and check if it is grammatical.
In the late 1950's, [[John Backus]] and Peter Naur developed a notation for describing [[programming language]]s. This notation is known as [[Backus Naur Form]] (or BNF) and turns out to be equivalent to Chomsky's grammar number two (context-free grammar), although it was developed independently of Chomsky's work. Backus-Naur Form was first used in the Algol 60 Report to specify the syntax of [[Algol 60]], and has since been used for specifying the syntax of other programming languages.
In the late 1950s, [[John Backus]] and Peter Naur developed a notation for describing [[programming language]]s. This notation is known as [[Backus-Naur Form]] (or BNF) and turns out to be equivalent to Chomsky's grammar number two (context-free grammar), although it was developed independently of Chomsky's work. Backus-Naur Form was first used in the Algol 60 Report to specify the syntax of [[Algol 60]], and has since been used for specifying the syntax of other programming languages.
==Example of a very simple generative grammar==
==Example of a very simple generative grammar==
==Formal grammar==
==Formal grammar==
'''Note''': this section and subsequent sections are, by necessity, slightly more technical/formal than the earlier parts of this article, though specialist notation has been largely avoided. 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, and variations on that example will be used to illustrate new ideas. An attempt has been made to avoid formal linguistic abbreviations and unexplained jargon.
'''Note''': this section and subsequent sections are, by necessity, slightly more technical/formal than the earlier parts of this article, though specialist notation and abbreviations have been largely avoided. 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, and variations on that example will be used to illustrate new ideas.
A formal generative grammar has four components (see slide 19 of this lecture
A formal generative grammar has four components (as described in 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
Notes:
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.
:Terminal items are those which can not be transformed into anything else.
:A list of all the terminal items is effectively the vocabulary from which sentences are built.
:A list of all the terminal items is effectively the vocabulary from which sentences are built.
:Non-terminal items are those which can be transformed into something else.
:Linguists have developed various classes of grammars by using constraints to govern what sort of rules can be used for any particular grammar.
:Linguists have developed various classes of grammars by using constraints to govern what sort of rules can be used for any particular grammar.
| accessdate = 2012-04-07
| accessdate = 2012-04-07
}}</ref>
}}</ref>
as to what sort of transformation rules could be used, Chomsky was able to define four strictly nested transformational grammars, which he numbered from 0 to 3. As the grammar number increases, the generated language becomes simpler. As the grammar number decreases, parsing a sentence in that language becomes more difficult. The following table provides a summary, which is then explained further in the subsequent subsections.
as to what sort of transformation rules could be used, Chomsky was able to define four strictly nested transformational grammars, which he numbered from 0 to 3. As the grammar number increases, the generated language becomes simpler. As the grammar number decreases, parsing a sentence in that language becomes more difficult.
Other linguists have described formal grammars which fit in between the various Chomsky levels.
The following table provides a summary, which is then explained further in the subsequent subsections.
{| class="wikitable"
{| class="wikitable"
In the linguistic literature, [nothing] is often represented by the symbol '''ε'''.
In the linguistic literature, [nothing] is often represented by the symbol '''ε'''.
The descriptions of the various Chomsky levels which follows are presented in reverse order, so as to work up from a simple case to a rather complicated case.
The descriptions of the various Chomsky levels which follow are presented in reverse order, so as to work up from a simple case to a rather complicated case.
===Level 3: regular grammar===
===Level 3: regular grammar===
''Expression'' -> ''Term'' # an ''Expression'' is either a ''Term''
''Expression'' -> ''Term'' # an ''Expression'' is either a ''Term''
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term'' # or an ''Expression'' followed by '''+''' or '''-''' followed by a ''Term''
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term'' # or an ''Expression'' followed by '''+''' or '''-''' followed by a ''Term''
#
''Term'' -> ''Primary'' # a ''Term'' is either a ''Primary''
''Term'' -> ''Primary'' # a ''Term'' is either a ''Primary''
''Term'' -> ''Term'' ''MulDivOp'' ''Primary'' # or a ''Term'' followed by '''*''' or '''/''' followed by a ''Primary''
''Term'' -> ''Term'' ''MulDivOp'' ''Primary'' # or a ''Term'' followed by '''*''' or '''/''' followed by a ''Primary''
-> '''2''' '''*''' '''3''' '''+''' '''4'''
-> '''2''' '''*''' '''3''' '''+''' '''4'''
===Level 1===
====Discussion====
Context-free grammars (or equivalent definitions using Backus-Naur-Form) are widely used both to define the syntax of programming languages and to (semi-automatically) generate parsers for these languages.
A limitation/feature of both regular grammars and context-free grammars is that the left-hand side of any rule is always a single non-terminal item, so any transformation is applied regardless of the context in which that non-terminal item appears. A simple example which depends on context is the use of singular and plural nouns and verbs in English. We say: '''the man runs''' or '''the men run''', but neither of '''the man run''' nor '''the men runs'''. Which form of verb to use depends on the noun, i.e. there is a context dependency.
For context-sensitive grammars the left-hand side of a rule may indicate the context in which that rule applies, so that the same non-terminal item may be transformed in different ways depending on the context in which it appears. Several examples appear in these lecture notes.
===Level 1: context-sensitive grammar===
For context-sensitive grammars the left-hand side of a rule may indicate the context in which that rule applies, so that the same non-terminal item may be transformed in different ways depending on the context in which it appears.
There is only one transformation rule for context-sensitive grammars:
*X [non-terminal] Y -> X [anything] Y
where X and Y determine the context in which the [non-terminal] is transformed. Note that X and Y may each be terminals or non-terminals or [nothing]. When both X and Y are nothing there is no context and this reduces to a Level 2 or Level 3 grammar.
====Example====
Taylor has provided several examples
<ref>{{cite web
<ref>{{cite web
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| title = Context-sensitive Examples
| title = Context-sensitive Examples
| author = Taylor
| accessdate = 2012-04-26
| accessdate = 2012-04-26
}}</ref>
}}</ref>
and the following, inspired by his third example, is an extension of the original simple example above to handle singulars and plurals:
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' # simple sentence structure
''NounPhrase'' -> ''Determiner'' ''Noun'' # simple phrase structure
''VerbPhrase'' -> ''Verb'' ''NounPhrase'' # simple phrase structure
#
''Noun'' -> ''SingularNoun'', ''PluralNoun'' # nouns can be singular or plural
#
''Determiner'' ''SingularNoun'' -> ''SingularDeterminer'' ''SingularNoun'' # context-sensitive:
''Determiner'' ''PluralNoun'' -> ''PluralDeterminer'' ''PluralNoun'' # determiner must agree with noun
#
''SingularNoun'' ''Verb'' -> ''SingularNoun'' ''SingularVerb'' # context-sensitive:
''PluralNoun'' ''Verb'' -> ''PluralNoun'' ''PluralVerb'' # verb must agree with noun
#
''SingularDeterminer'' -> '''a''', '''the''' # singular determiners
''PluralDeterminer'' -> '''the''' # plural determiners
#
''SingularNoun'' -> '''boy''', '''sheep''', '''dog''' # singular nouns
''PluralNoun'' -> '''boys''', '''sheep''', '''dogs''' # plural nouns
#
''SingularVerb'' -> '''chases''', '''hears''', '''sees''' # singular verbs
''PluralVerb'' -> '''chase''', '''hear''', '''see''' # plural verbs
===Level 0===
The above grammar can generate sentences such as: '''a boy chases a dog''', '''the boys chase a dog''', etc. Because some words have the same form in both singular and plural, it can also generate meaningful (and grammatically-correct) sentences such as: '''the sheep sees the dog''', '''the sheep see the dog'''.
But the above grammar can NOT generate sentences such as: '''a boys chases the sheep''', since this would violate the context-sensitive rules.
====Discussion====
It is in fact possible to handle singular/plural issues by using only a Level 2 context-free grammar, but the above rules expressed as a Level 1 context-sensitive grammar are a closer match to ordinary concepts of English grammar (e.g. nouns and verbs must agree in number i.e. singular/plural).
===Level 0: recursively enumerable grammar===
A recursively enumerable grammar has absolutely no restriction on what sort of transformation rules can be applied; hence it is also known as an unrestricted grammar. Rules take the general form:
*[anything] -> [anything]
====Example====
The following rules can generate all symbols of the form: abc, aabbcc, aaabbbccc, etc., where there are equal numbers of a's, b's and c's. This example is taken from a lecture.<ref>{{cite web
| url = http://www.cs.utexas.edu/~cline/ear/Slides/Turing/TuringSlides3.doc
| title = Grammars, Recursively Enumerable Languages, and Turing Machines
| accessdate = 2012-05-10
}}</ref>
''S'' -> '''a''' ''B'' ''S'' '''c'''
''S'' -> '''a''' ''B'' '''c'''
''B'' '''a''' -> '''a''' ''B''
''B'' '''c''' -> '''b''' '''c'''
''B'' '''b''' -> '''b''' '''b'''
The derivations of the first three items in this infinite sequence are:
# ''S'' -> '''a'''''B'''''c''' -> '''abc'''
# ''S'' -> '''a'''''BS'''''c''' -> '''a'''''B'''''a'''''B'''''cc''' -> '''aa'''''B B'''''cc''' -> '''aa'''''B'''''bcc''' -> '''aabbcc'''
# ''S'' -> '''a'''''BS'''''c''' -> '''a'''''B'''''a'''''BS'''''cc''' -> '''a'''''B'''''a'''''B'''''a'''''B'''''ccc''' -> '''aa'''''BB'''''a'''''B'''''ccc''' -> '''aa'''''B'''''a'''''BB'''''ccc''' -> '''aaa'''''BBB'''''ccc''' -> '''aaa'''''BB'''''bccc''' -> '''aaa'''''B'''''bbccc''' -> '''aaabbbccc'''
===Beyond Level 0===
These lecture notes
<ref>{{cite web
| url = http://www.google.co.uk/url?sa=t&rct=j&q=recursively+enumerable+languages+examples&source=web&cd=4&ved=0CF4QFjAD&url=http%3A%2F%2Fwww.cs.colostate.edu%2F~massey%2FTeaching%2Fcs301%2FRestrictedAccess%2FSlides%2F301lecture23.pdf&ei=6qelT4KMA6SA0AXIu7CQBA&usg=AFQjCNG3fc1mD7g5f-14vfDPdvyX2uScDg
| title = Recursive and Recursively Enumerable Languages
| accessdate = 2012-05-05
}}</ref>
show that languages exist which can not be described by any set of rules. As is common with logical proofs of this nature, the proof doesn't actually produce or demonstrate such a language.
==References==
==References==
<references/>
<references/>
[[category:linguistics]]
[[Category:Linguistics]]
[[Category:Computer Science]]
[[Category:Computer Science]]
[[Category:Language]]