Classification of Context Free Grammar:
From the behavior of the production rules of the context free grammar, we classify it into two different form are as follows;
- Right-Linear Grammar
- Left-Linear Grammar
Right-Linear Grammar:
In right-linear grammar, all productions have one of the two forms:
V → T* V
or V → T*
i.e., the left hand side should have a single variable symbol and the right hand side consists of any number of terminals (members of T) optionally followed by a single variable symbol.
For example:
Right Linear Grammar | DFA |
A → xB | |
A → xyzB | |
A → B | |
A → x |
Left-Linear Grammar:
In a left-linear grammar, all productions have one of the two forms:
V → VT*
or V → T*
i.e., the left hand side must consist of a single variable symbol, and the right-hand side consists of an optional single variable symbol followed by one number of terminals.