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

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

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:

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]

*[anything] -> [anything]

===Beyond Level 0===

===Beyond Level 0===

<references/>

<references/>

[[category:linguistics]]

[[Category:Linguistics]]

[[Category:Computer Science]]

[[Category:Computer Science]]