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

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

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

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

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

 

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

{| class="wikitable"

{| class="wikitable"

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

But the above grammar can NOT generate sentences such as: '''a boys chases the sheep''', since this would violate the context-sensitive rules.

But the above grammar can NOT generate sentences such as: '''a boys chases the sheep''', since this would violate the context-sensitive rules.

===Level 0===

 

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

 

 

 

 

 

| 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

==References==

==References==

<references/>

<references/>

[[category:linguistics]]

[[Category:Linguistics]]

[[Category:Computer Science]]

[[Category:Computer Science]]