The Chomsky Hierarchy of Grammars

The Chomsky Hierarchy of Grammars

A hierarchy of classes of languages viewed as sets of strings, ordered by their “complexity”. The high er the language is in the hierarchy, the more complex it is. In particular the class of languages in one class properly includes the languages in lower classes. There exists a correspondence between the class of languages and the format of phrase structure rules necessary for generating all its languages. Noam Chomsky defined a hierarchy of grammars called Type 0, Type 1, Type 2 and Type 3. The outline of Chomsky hierarchy of languages is given in figure .

The Chomsky hierarchy of languages reflects a certain order of complexity in s ome sense, the lower the language class is in the hierarch y; the simplest are its possible constructions.

1.    Type 0 (Recursively E numerable Languages): It is obtained by makin g the simple restrictions that cannot be empty string in the rewrite form abc → adc. It is the much more simplest grammar than others.

2.    Type 1 (Context Sensitive Languages): They have added restriction th at the length of the string on the right hand side o the rewrite rule must be at least as long as the strings on the left side. In production of the form in , b must be a single non termina l symbol and d is a non 

empty string.

For example:

So we can say that always a terminal symbol should start first (like ‘b’) then any no. of symbols may come.

Some symbols are used to represent the grammars and they are described as follows.

·        Sentences ® S

·        Verb Phrase ® VP

·        Noun Phrase ® NP

·        Preposition Phrase ® PP

·        Auxiliary ® AUX

·        Preposition ® PREP

·        Adverb ® ADV

·        Adjectives ® ADJ

·        Determiners ® DEJ

·        Article ® ART

·        Noun ® N

·        Verb ® V and so on.

Also while representing a sentence we have to follow some rules like as follows.

By taking into consideration the above rules any types of syntactic grammars are possible. Always you have to remember a sentence must have at least two clauses like verb phrase (VP) and noun phrase (NP). Now let us see some other types of grammars used in language processing like transformational grammar, case grammar, systemic grammar and semantic grammar etc.