Chomsky Classification of Grammars – Tutorial
Chomsky Classification of Grammars
According to Noam Chomosky, there are four types of grammars – Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other –
|Grammar Type||Grammar Accepted||Language Accepted||Automaton|
|Type 0||Unrestricted grammar||Recursively enumerable language||Turing Machine|
|Type 1||Context-sensitive grammar||Context-sensitive language||Linear-bounded automaton|
|Type 2||Context-free grammar||Context-free language||Pushdown automaton|
|Type 3||Regular grammar||Regular language||Finite state automaton|
Take a look at the following illustration. It shows the scope of each type of grammar –
Type – 3 Grammar
Type-3 grammars generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.
The productions must be in the form X â a or X â aY
where X, Y â N (Non terminal)
and a â T (Terminal)
The rule S â Îµ is allowed if S does not appear on the right side of any rule.
X â Îµ X â a | aY Y â b
Type – 2 Grammar
Type-2 grammars generate context-free languages.
The productions must be in the form A â Î³
where A â N (Non terminal)
and Î³ â (T âª N)* (String of terminals and non-terminals).
These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.
S â X a X â a X â aX X â abc X â Îµ
Type – 1 Grammar
Type-1 grammars generate context-sensitive languages. The productions must be in the form
Î± A Î² â Î± Î³ Î²
where A â N (Non-terminal)
and Î±, Î², Î³ â (T âª N)* (Strings of terminals and non-terminals)
The strings Î± and Î² may be empty, but Î³ must be non-empty.
The rule S â Îµ is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.
AB â AbBc A â bcA B â b
Type – 0 Grammar
Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.
They generate the languages that are recognized by a Turing machine.
The productions can be in the form of Î± â Î² where Î± is a string of terminals and nonterminals with at least one non-terminal and Î± cannot be null. Î² is a string of terminals and non-terminals.
S â ACaB Bc â acB CB â DB aD â Db