A grammar G is 4-tuple or quadruple G=(V,T,P,S) where
V is set of variables or non-terminals.
T is set of terminals.
P is set of productions.
S is the start symbol.
Each production is of the form α -> β where α is a non empty string of terminals and/or non-terminals and β is string of terminals and/or non-terminals including the null string. This grammar is also called as phase-structure grammar.
T is set of terminals.
P is set of productions.
S is the start symbol.
Each production is of the form α -> β where α is a non empty string of terminals and/or non-terminals and β is string of terminals and/or non-terminals including the null string. This grammar is also called as phase-structure grammar.
CHOMSKY HIERARCHY
Phase-structure grammars may be classified according to their productions. The following table would help you understand with the classifications.| S.no | TYPE | NAME | PRODUCTION RULE | RESTRICTION | LANGUAGE GENERATED | MACHINE WHICH RECOGNISES |
|---|---|---|---|---|---|---|
| 1 | Type 0 grammar | Unrestricted grammar | α -> β | No restriction on length of α and β.α cannot be epsilon | type o language or recursively enumerable language | Turing machine |
| 2 | Type 1 grammar | Context sensitive grammar | α -> β | Length of β must be atleast as much as the length of α | Type 1 language or context sensitive language | Linear Bounded automata |
| 3 | Type 2 grammar | Context free grammar | A->α | The symbol epsilon can appear on the right side of any production. | type 2 language or context free language | Pushdown automaton |
| 4 | Type 3 grammar | Regular grammar | A->wB and/or A->w | Regular language | Finite state automaton |
No comments:
Post a Comment