Match the following : List-I
Match the following :
List-I
(A) Chomsky Normal form
(B) Greibach Normal form
(C) S-grammar
(D) LL grammar
List-II
(i) S → b S S | a S | c
(ii) S → a S b | ab
(iii) S → AS | a ; A → SA | b
(iv) S → a B S B ; B → b
Codes : A B C D
Show answerHide answer
Correct answer: (C) iii iv i ii
Explanation
Chomsky Normal Form : production rules are of the form A → BC or A → a (and S → ε) — grammar (iii). Greibach Normal Form : production rules are of the form A → aA₁A₂...Aₙ or A → a — grammar (iv). S-grammar : every production's right-hand side begins with a terminal, and this terminal is different for any two productions with the same left-hand side — grammar (i). LL grammar : two production rules for the same nonterminal can begin with the same terminal only if their select sets differ — grammar (ii). So A-iii, B-iv, C-i, D-ii, i.e. option (c).