Block, SkipCaptcha, apieditor, Automoderated users, Bots, edit, ratelimit-exempt
59,081
edits
Changes
Jump to navigation
Jump to search
Line 1:
Line 1: − + Line 14:
Line 14: + + Line 95:
Line 97: − + − + Line 110:
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 125:
Line 127: − + Line 137:
Line 139: − + + − 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. + Line 157:
Line 160: − + Line 205:
Line 208: − + − + Line 214:
Line 217: − + − + − + − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + − ''Primary'' -> ''Number''+ − ''Primary'' -> '''(''' ''Expression'' ''')'''+ + + + + − + − + − + + + − ===Level 1===+ − + + + + + + + + + + + + − + +
→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 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.
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.
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 in this example generate exactly the same sentences.
The above change is known as right-recursive; a left-recursive formulation is also possible, and can in this example generate exactly the same sentences. As shown below under 'Context-free grammar', there are situations where the choice of left- or right-recursive formulations can change the meaning.
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'', ''Sentence'' '''and''' ''NounPhrase'' ''VerbPhrase''
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'', ''Sentence'' '''and''' ''NounPhrase'' ''VerbPhrase''
| 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===
====Example====
====Example====
The following example shows how context-free grammars can cope with arithmetic expressions involving possibly nested brackets. Also an expression such as "2 + 3 * 4" could be interpreted as either "(2 + 3) * 4" or as "2 + (3 * 4)". The latter interpretation is that which is normally used - multiplication "*" is said to have a higher priority than addition "+" - so the example also needs to incorporate this priority concept into the grammar. Furthermore, consecutive operators of the same priority are applied from left to right, so that "8 - 2 + 3" is interpreted as "(8 - 2) + 3" = 9, rather than as "8 - (2 + 3)" = 3. This ordering must also be built in to the grammar.
The following example shows how context-free grammars can cope with arithmetic expressions involving possibly nested brackets. Also an expression such as "2 + 3 * 4" could be interpreted as either "(2 + 3) * 4" = 20 or as "2 + (3 * 4)" = 14. The latter interpretation is that which is normally used - multiplication "*" is said to have a higher priority than addition "+" - so the grammar must incorporate this priority concept. Furthermore, consecutive operators of the same priority are normally applied from left to right, so that "8 - 2 + 3" is interpreted as "(8 - 2) + 3" = 9, rather than as "8 - (2 + 3)" = 3. This ordering must also be built in to the grammar.
To avoid distracting side-issues, this example only deals with numbers which consist solely of a single digit. The example is a simplified version of the definition of an arithmetic expression given in the Revised Algol 60 Report (Section 3.3.1)
To avoid distracting side-issues, this example only deals with numbers which consist solely of a single digit. The example is a simplified version of the definition of an arithmetic expression given in the Revised Algol 60 Report (Section 3.3.1).
<ref>{{cite web
<ref>{{cite web
| url = http://www.masswerk.at/algol60/report.htm
| url = http://www.masswerk.at/algol60/report.htm
}}</ref>
}}</ref>
''Expression'' -> ''Term''
''Expression'' -> ''Term'' # an ''Expression'' is either a ''Term''
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term''
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term'' # or an ''Expression'' followed by '''+''' or '''-''' followed by a ''Term''
''Term'' -> ''Primary''
#
''Term'' -> ''Term'' ''MulDivOp'' ''Primary''
''Term'' -> ''Primary'' # a ''Term'' is either a ''Primary''
''Term'' -> ''Term'' ''MulDivOp'' ''Primary'' # or a ''Term'' followed by '''*''' or '''/''' followed by a ''Primary''
#
''Primary'' -> ''Number'' # a ''Primary'' is either a ''Number''
''Primary'' -> '''(''' ''Expression'' ''')''' # or an ''Expression'' enclosed in brackets
#
''MulDivOp'' -> '''*'''. '''/''' # multiplication and division have the same priority
''AddSubOp'' -> '''+'''. '''-''' # addition and subtraction have the same priority
''Number'' -> '''0''', '''1''', ... '''9''' # this simple-minded definition of a ''Number'' is enough for this example
Notes:
* Both ''Expression'' and ''Term'' are each defined via a left-recursive rule; this ensures that operators of the same priority are applied from left to right.
* The distinction between ''Expression'' and ''Term'' ensures that multiplication/division are applied before addition/subtraction.
* ''Expression'' is indirectly recursive via ''Term'' and ''Primary'' to allow bracketed sub-expressions to any depth.
Example 1: generate 2 + 3 * 4
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term''
-> ''Term'' ''AddSubOp'' ''Term''
-> ''Primary'' ''AddSubOp'' ''Term''
-> '''2''' '''+''' ''Term'' # '''+''' can not be applied until ''Term'' has been evaluated
-> '''2''' '''+''' ''Term'' ''MulDivOp'' ''Primary''
-> '''2''' '''+''' ''Primary'' ''MulDipOp'' ''Primary''
-> '''2''' '''+''' '''3''' '''*''' '''4'''
Example 2: generate 2 * 3 + 4
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term''
-> ''Term'' ''AddSubOp'' ''Term''
-> ''Term'' ''MulDivOp'' ''Primary'' ''AddSubOp'' ''Term''
-> ''Primary'' ''MulDivOp'' ''Primary'' ''AddSubOp'' ''Term''
-> '''2''' '''*''' '''3''' ''AddSubOp'' ''Term'' # ''Term'' to left of ''AddSubOp'' is evaluated first
-> '''2''' '''*''' '''3''' ''AddSubOp'' ''Primary''
-> '''2''' '''*''' '''3''' '''+''' '''4'''
====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.
===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
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| title = Context-sensitive Examples
| author = Taylor
| accessdate = 2012-04-26
}}</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
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>
''MulDivOp'' -> '''*'''. '''/'''
''S'' -> '''a''' ''B'' ''S'' '''c'''
''AddSubOp'' -> '''+'''. '''-'''
''S'' -> '''a''' ''B'' '''c'''
''Number'' -> '''0''', '''1''', ... '''9'''
''B'' '''a''' -> '''a''' ''B''
''B'' '''c''' -> '''b''' '''c'''
''B'' '''b''' -> '''b''' '''b'''
The derivations of the first three items in this infinite sequence are:
===Level 0==
# ''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]]