Famous linguist Noam Chomsky divided formal grammar into four different classes in 1956. He listed the different classes of language it generates, the kind of automation that recognizes it, and the forms of its rules. The four types are – Type 0- Type 3. Let’s learn a little more in detail about them –
- Type 0 or the Recursively Enumerable Languages – These contain all formal grammars which are recognized by the turing machine.
- Type 1 or Context Sensitive Grammar – Linear Bound Automata recognizes this type of language. In order to qualify for Type 1, language must essentially be Type 0.
- Type 2 or Context Free Grammar – For language to be classified as Type 2, it must meet the following criteria i.e, it must be type 1 and left hand side of production can only have a singular variable. Type 2 Grammar is recognized by Pushdown Automata.
- Type 3 or Regular Grammar – Type 3 grammar includes all regular languages which can be accepted by a finite state automation. It is the most restricted form of grammar out of the abovelisted forms.
The distinction made between the different types of language can be easily observed by looking at the structure of the production rules of their individual grammar.