Chomsky Hierarchy
- Type 0 or Unrestricted Grammrs
- Type 1 or Context Sensitive Grammars
- Type 2 or Context Free Grammars
- Type 3 or Regular Grammar
Unrestricted Grammar ( or Type 0 grammar)
A grammar G = (V, T, P, S) is called unrestricted if all the productions are of the form,
α→β
where α is in (VUT)+ ( i.e., it can be a string of terminals or non-terminals with at least one non-terminal ) and β is in (VUT)* (a string of terminals and non-terminals ).
Any language generated by an unrestricted grammar is recursively enumerable that are recognized by Turing Machine.
For example,
S→AaB
A→S
Bc→acB
Context Sensitive Grammars ( or Type 1 grammars )
A grammar G = (V, T, P, S ) is said to be context sensitive if all productions are of the form,
α→β
where α, β ∈ (VUT)+ and |α| ≤ |β|
( Except for S→∈ and start symbol S does not appear on the right hand side of any production )
This type of grammar generate context sensitive language that are recognized by Linear Bounded Automata.
For example,
S→AB
AB→abc
B→b
Context Free Grammars ( or Type 2 grammars )
A grammar G = (V, T, P, S) is said to be context free if all productions are of the form,
α→β
where α ∈ V and β ∈ (VUT)* .
This type of grammar generate context free language that are recognized by Non Deterministic Push Down Automata.
For example,
S→AB
A→x
B→y
Regular Grammar ( or Type 3 grammar )
A grammar G = (V, T, P, S) is said to be context free if all productions are of the form,
α→β
where α ∈ V and β ∈ VT* + T* or β ∈ T* V + T* ( i.e., grammar must have a single terminal on left hand side and on right hand side must have a single non-terminal followed by a terminal ( 0 or more ) or terminal ( 0 or more ) followed by a single non-terminal.
If variable(V of β) is on left then its left linear grammar and if variable is on right then its right linear grammar.
Type 3 generates regular languages that is recognized by Finite Automata.
For example,
S→aS | bS | ∈