UGC NET CSE | June 2012 | Part 3 | Question: 28

Question

Which one of the following is not a Greibach Normal form grammar?

(i)	$S \rightarrow a \mid bA \mid aA \mid bB$ $A \rightarrow a$ $B \rightarrow b$
(ii)	$S \rightarrow a \mid aA \mid AB$ $A \rightarrow a$ $B \rightarrow b$
(iii)	$S \rightarrow a \mid A \mid aA $ $A \rightarrow a$

• A. (i) and (ii)
• B. (i) and (iii)
• C. (ii) and (iii)
• D. (i), (ii) and (iii)

Answer 1

A context free Grammar is said to be Greibach normal form if all the productions have the form

A $\rightarrow$ ax

where a∈ T and x∈ v^*

(ii)Eliminate due to production $S\rightarrow AB$

(iii)Eliminate Due to production$S\rightarrow A$

only(1) Satisfying the required conditions. 

Hence,Option(C)ii and (iii) is the correct choice.

Answer 2

Greibach Normal Form Grammar  :- A CFG  G=(V,T,S,P) is called GNF  if all production have the form 

A->ax where  a belongs to T(terminals) and X belongs to V* here restriction is on the position of terminal and symbol(i.e terminals must present and present before symbol if any) and not on the length.

Now in above options  choice 2 and 3  productions S->AB and S->A which violates above condition hence ans is C