Changes

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==

'''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.  

'''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

}}</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.

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. This lecture

Other linguists have described formal grammars which fit in between the various Chomsky levels.  

shows that there exist languages which can not be described by any set of rules.

The following table provides a summary, which is then explained further in the subsequent subsections.

The following table provides a summary, which is then explained further in the subsequent subsections.

  ''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''

There is only one transformation rule for context-sensitive grammars:

There is only one transformation rule for context-sensitive grammars:

 

*X [non-terminal] Y -> X [anything] Y

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.

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.

===Level 0: recursively enumerable grammar===

===Level 0: recursively enumerable grammar===

A recursively enumerable grammar has absolutely no restriction on what sort of transformation rules can be applied. Rules take the general form:

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]

''S''  -> '''a''' ''B'' ''S'' '''c'''

 

 

 

==References==

==References==

<references/>

<references/>

[[category:linguistics]]

[[Category:Linguistics]]

[[Category:Computer Science]]

[[Category:Computer Science]]