Which one of the following is not a Greibach Normal form grammar?
2012
Which one of the following is not a Greibach Normal form grammar?
- A.
(i) and (ii)
- B.
(i) and (iii)
- C.
(ii) and (iii)
- D.
(i), (ii) and (iii)
Attempted by 48 students.
Show answer & explanation
Correct answer: C
Greibach Normal Form (GNF) requires all productions to be of the form A -> aα, where a is a terminal and α consists of zero or more non-terminals.
In grammar (i), all productions start with a terminal (a or b), so it is in GNF.
In grammar (ii), the production S -> AB starts with a non-terminal, violating GNF.
In grammar (iii), the production S -> A starts with a non-terminal, violating GNF.
Therefore, grammars (ii) and (iii) are not in Greibach Normal Form.
A video solution is available for this question — log in and enroll to watch it.