UGC NET CSE | June 2014 | Part 3 | Question: 74

Question

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}$

$\textbf{Codes :}$

• A. $\text{a-iv, b-iii, c-i, d-ii}$
• B. $\text{a-iv, b-iii, c-ii, d-i}$
• C. $\text{a-iii, b-iv, c-i, d-ii}$
• D. $\text{a-iii, b-iv, c-ii, d-i}$

Answer 1

a) In Chomsky normal form  all of its production rules should be of the form:

A → BC,   or

A → a,   or

S → ε,

iii satisfies this

 

b) In  Greibach normal form, if all production rules are of the form:

A → aA1A2...An or

A → a

iv satisfies this

c) A context free grammar is an s-grammar if and only if every production's right hand side begins with a terminal symbol and this terminal is different for any two productions with the same left-hand side.

i satisfies this

 

d) In LL grammar, two production rules can begin  with same terminal symbols if they have same select sets.

ii satisfies this

 

ANSWER :C