Past exam question: 2082 Kartik (Back), Q3(c)(i)
Open in the Padhaiko appQuestion
Define Greibach Normal Form (GNF).
Solution
Definition and Formal Constraints of GNF: A Context-Free Grammar is in Greibach Normal Form (GNF) if every production rule in is of the form:
where:
- is a single non-terminal (variable),
- is a single terminal symbol,
- is a (possibly empty) sequence of non-terminals.
If the language contains the empty string (), the production is permitted, provided the start symbol does not appear on the right-hand side of any production rule.
Key Significance: In GNF, every derivation step consumes exactly one input terminal symbol, guaranteeing that any string of length is derived in exactly steps without left-recursion.
Answer:
A CFG is in Greibach Normal Form (GNF) if all productions are of the form , where is a single terminal and is a string of zero or more non-terminals ( allowed if ).