Chomsky Hierarchy
Noam Chomsky has classified all grammars in four categories
- Type 0.(phrase structured grammars).
- Type 1.(Context sensitive grammars).
- Type 2.(Context free grammars).
- Type 3.(Regular grammars).
Type 0:- Type 0 grammer is also known as phrase structured grammar and recursive enumerable grammar.Right-hand side of these rules of these grammers are free from any restriction.That language is accepted by turing machine.
∝-->β
∝∈(∑⋃ N)*N(∑⋃ N)*
β∈(∑⋃ N)*
Example:
AS->aS
SB->Sb
Type 1:-That is also called context sensitive grammar and length increasing grammar. That language is accepted by pushdown automata(PDA).In this grammer production rule ∝-->β is restricted such that
|∝|<=β and β≠∈ then this type of production are known as type1 grammar. The production S->∈ is allowed in type1 .
∝-->β
∝∈(∑⋃ N)*N(∑⋃ N)*
β∈(∑⋃ N)+
Example:
S->AB
S->∈
A->c
That all are type1 production.
Type 2:-Restricted form of Type1 production rule are known as type2 or context free production.It generates context free language which is accepted by push down automata.
∝-->β
∝∈N ,|∝|=1
β∈(∑⋃ N)*
Example:
S->S+S
S->S*S
S->id
That all are Type2 production.
Type3:-This is most restricted type.productions of type
A->a
A->aB|Ba
that are type3 or regular grammar production rule.
production S->∈ is also allowed in type3 .
Left linear:-A production rule of type A->Ba is called left linear production rule. Where A and B are variable and a is terminal.
Right linear:- A production rule of type A->aB is called right-linear production rule where A and B are variable and a is terminal.
Left linear and right linear grammar is called regular grammar.The language generated by regular grammar is known as regular language.
Hierarchy of grammars
0 Comments