ans is C it is in GNF and also produces the strings of type
anbn+1∣n≥0
choice A and B are in GNF but do not produce the above language as S is non terminating
choice D is not in GNF as S->aSb is a violation of GNF
A CFG is said to be in Greibach normal form (GNF)
if all productions have the form
A->ax
where a ∈ T , x∈V* i.e terminal and vertices respectively
or
n formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.
More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:
- {\displaystyle A\to aA_{1}A_{2}\cdots A_{n}} or S->∈
ab