1. Type-0 (Unrestricted Grammar)
2. Type-1 (Context Sensitive Grammar)
3. Type-2 (Context Free Grammar)
4. Type-3 (Restricted Grammar)
1. Type-0 Grammar:
Type-0 grammar also called Unrestricted Grammar is implemented by using an Turing Machine. The Type-0 grammar can represent all types of grammars possible. It is also called Recursively Enumerable Grammar.
This grammar is in the form of :
A -> B
where A is the combination of Non-terminals and Terminals with at least one non-Terminal i.e. (N+T)*N(N+T)*
and B is simply the combination of Non-terminals and Terminals
Example:
Aa -> B
ASb->a
aBa->S
2. Type-1 Grammar :
Type-1 grammar also called Context Sensitive Grammar is implemented using Linear Bound Automaton. In order to be in Type-1 Grammar, it must be in Type-0 first.
This grammar is in the form of :
A -> B
where A and B are same as in the Type-0 grammar but the number of symbols in A is less than or equal to that in B i.e. |A| <= |B|
Example:
Ab->aBa
B->Aa
S->AB
3. Type-2 Grammar:
Type-2 grammar also called Context Free Grammar is implemented using Push Down Automaton. In order to be in Type-2 Grammar, it must first be in Type-1.
This grammar is in the form of:
A-> B
where A is a non-terminal and B is the combination of Terminals and non-Terminals
Example:
S -> aA
A -> Ba
B -> ABa
4. Type-3 Grammar :
Type-3 grammar also called Restricted Grammar is implemented using an Finite State Automaton. This is the most restricted grammar. In order to be in this type, the grammar must be in either of the following type:
N -> NT* / T*
i.e.On the left - an non-terminal
and on the right - begin with non-terminal followed by combination of terminals or just the combination of terminals
OR,
N - > T*N / T*
i.e.On the left - an non-terminal
and on the right - begin with combination of terminals followed by an Non-Terminal or just the combination of terminals
Example:
S -> Aa
A -> ab
OR,
S -> aA
A -> ab
No comments:
Post a Comment