Chomsky hierarchy of grammar
Chomsky hierarchy of grammars
With the help of Chomsky hierarchy of grammars, we can exhibit the relationship between grammars and can classify them into four types of grammar as below:
- Type 0: unrestricted/phase structure grammar.
- Type 1: context sensitive grammar.
- Type 2: context free grammar.
- Type 3: regular grammar.
 |
| Classification of grammars |
Let us study each of the classified grammars one by one in brief.
Unrestricted grammars (Type 0)
The unrestricted grammar is defined as
G = (Vn, Vt, P, S)
where,
Vn = a finite set of non-terminals.
Vt = a finite set of terminals.
S = starting non-terminals. So S∈Vn
and P is set of production rule of the following form:
α→ß
where are α and ß and arbitrary strings of grammar symbols with α≠∈.
This type of grammar is also known as type=0, phase structure or unrestricted grammar.
where,
Vn = a finite set of non-terminals.
Vt = a finite set of terminals.
S = starting non-terminals. So S∈Vn
and P is set of production rule of the following form:
α→ß
where are α and ß and arbitrary strings of grammar symbols with α≠∈.
This type of grammar is also known as type=0, phase structure or unrestricted grammar.
Context sensitive grammar (Type 1)
Let G = (Vn, Vt, P, S)
where,
Vn = a finite set of non-terminals.
Vt = a finite set of terminals.
S = starting non-terminals. So S∈Vn
and P is set of production rule of the following form:
α→ß
where ß is at least as long as ɑ that is clearly
|α|≤|ß|
The term context-sensitive refers to the normal form of grammar where each production is of the form α1Aα2 → α1ßα2, where ß≠∈.
Replacement of variable A by string ß is permitted in the context of α1 and α2.
where,
Vn = a finite set of non-terminals.
Vt = a finite set of terminals.
S = starting non-terminals. So S∈Vn
and P is set of production rule of the following form:
α→ß
where ß is at least as long as ɑ that is clearly
|α|≤|ß|
The term context-sensitive refers to the normal form of grammar where each production is of the form α1Aα2 → α1ßα2, where ß≠∈.
Replacement of variable A by string ß is permitted in the context of α1 and α2.
Context-free grammar (Type 2)
The context free grammar can be defined as
G = (Vn, Vt, P, S)
where,
Vn = a finite set of non-terminals.
Vt = a finite set of terminals.
S = starting non-terminals. So S∈Vn
and P is set of production rule of the following form:
α→ß
G = (Vn, Vt, P, S)
where,
Vn = a finite set of non-terminals.
Vt = a finite set of terminals.
S = starting non-terminals. So S∈Vn
and P is set of production rule of the following form:
α→ß
where α∈Vn and ß∈(Vt ∪ Vn)*
Regular grammar (Type 3)
A regular grammar is of two types: left linear or right linear.
It can be defined by the following:
- If all production of the CFG are in the form of A→wB or A→w, where A and B are variables and w∈Vt*, then we can say that the grammar is right linear.
- If all production of the CFG are in the form of A→Bw or A→w, where A and B are variables, then we can say that the grammar is left linear.
No comments: