Match the following : \(\begin{array}{clcl} & \textbf{List – I} & &…
2014
Match the following :
\(\begin{array}{clcl} & \textbf{List – I} & & \textbf{List – II} \\ \text{a.} & \text{Chomsky Normal form} & \text{i.} & S \rightarrow b S S \mid a S \mid c \\ \text{b.} & \text{Greibach Normal form} & \text{ii.} & S \rightarrow a S b \mid ab \\ \text{c.} & \text{S-grammar} & \text{iii.} & S \rightarrow AS \mid a \\ & & & A \rightarrow SA \mid b \\ \text{d.} & \text{LL grammar} & \text{iv.} & S \rightarrow a B S B \\ & & & B \rightarrow b \\ \end{array}\)
Codes :
- A.
a-iv, b-iii, c-i, d-ii
- B.
a-iv, b-iii, c-ii, d-i
- C.
a-iii, b-iv, c-i, d-ii
- D.
a-iii, b-iv, c-ii, d-i
Attempted by 79 students.
Show answer & explanation
Correct answer: C
Match each grammar class to the grammar that satisfies its defining property.
a. Chomsky Normal Form → (iii) S → AS | a ; A → SA | b. CNF allows only productions of the form A → BC (two variables) or A → a (one terminal). Here S → AS and A → SA are two-variable productions, while S → a and A → b are single terminals, so this grammar is in CNF.
b. Greibach Normal Form → (iv) S → a B S B ; B → b. GNF requires every right-hand side to begin with a terminal followed by zero or more variables. S → a B S B starts with terminal 'a' followed by variables, and B → b is a single terminal, so this grammar is in GNF.
c. S-grammar → (i) S → b S S | a S | c. A simple (s-)grammar requires every production to begin with a terminal and, for each variable, all alternatives to begin with distinct terminals. The three S-alternatives begin with b, a, and c — all different — so this is an s-grammar.
d. LL grammar → (ii) S → a S b | ab. This is the remaining grammar. Note that S → a S b | ab has both alternatives starting with 'a', so it is not an s-grammar (which is why it cannot match c); it is paired here with the LL-grammar entry.
Correct matching: a–iii, b–iv, c–i, d–ii.