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 GrammarDFA
A → xB

Right Linear Grammar DFA
Right Linear Grammar DFA State to state transaction
A → xyzB

Right Linear Grammar DFA
Right Linear Grammar DFA to accept string and state
A → B

Right Linear Grammar DFA
Right Linear Grammar DFA to state switch without any input string
A → x

Right Linear Grammar DFA
Right Linear Grammar DFA to reach final state with accepting input string

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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.