Types of Grammar and Chomsky's Hi Hierarchy of Languages

Types of Grammar and Chomsky's Hi Hierarchy of Languages

The Chomsky's Hierarchy represents the class of languages that are accepted by different machine. The category of languages in Chomsky's Hierarchy is as given below –

This is a hierarchy therefore every language of type 3 is also of type 2, 1 and 0. Similarly every language of type 2 is also of type 1 and 0 etc.

Type 3 Regular languages

Regular languages are those languages which can be described using regular expressions. These languages can be modelled by NFA or DFA.

Type 2 Context free languages

The context free languages are the languages which can be represented by Context Free Grammar (CFG). The production rule is of the form

Α → α

where A is any single non-terminal and a is any combination of terminals and non-terminals.

A NFA or DFA cannot recognize strings of this language because these automata are not having "stack" to memorize. Instead of it the Push Down Automata can be used to represent these languages.

Type 1 - Context sensitive languages

The context sensitive grammars are used to represent context sensitive languages. The context sensitive grammar is follows the following rules -

1. The context sensitive grammar may have more than one symbol on the left hand side of their production rules.

2. The number of symbols on the left hand side must not exceed the number of symbols on the right hand side.

3. The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right hand side of any rule.

The automaton which recognizes context sensitive languages is called linear bounded automaton. While deriving using context sensitive grammar the sentential form must always increase in length every time a production rule is applied. Thus the size of a sentential form is bounded by a length of the sentence we are deriving.

Type 0 Unrestricted languages