PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q3(c)(i)

Theory of Computation · 1 marks

Open in the Padhaiko app

Topic: Simplification of CFG; CNF, GNF & BNF

Question

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:

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 ).

All past exam questions for Theory of Computation