Greibach Normal Form

In Automata, every context free grammar can be converted into Greibach Normal Form. A context-free grammar is said to be in Greibach Normal Form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. The name Greibach Normal Form came from the name Sheila Greibach. She was the Emeritus Professor of Computer Science and established the Greibach Normal Form for context free grammars.

A context free grammar G = (V,Σ,P,S) is said to be in Greibach Normal Form if all of its production rules are in the form-

A → aBC, A → aB, A → a, or S → ε

Here, A, B and C are non-terminal symbols, where A,B,C ∈ N,
a is the terminal symbol, where a ∈ Σ,
S is the start symbol, where S → ε and
ε is the empty string.





Process to find Context Free Grammar in Greibach Normal Form

The symbol S does not occur on the right hand side of any productions. The grammar does not have ε rules and every rule produces some terminal symbol other than S → ε. The most important consequence of this form is that every nonterminal is not left recursive. The Greibach Normal Form provides a solution of avoiding the left recursive approach because non-terminal left recursive.





Read more articles


General Knowledge



Learn Popular Language