Match List I with List II Choose the correct answer from the options given…
2021
Match List I with List II
Choose the correct answer from the options given below :
- A.
A ‐ III, B ‐I , C ‐ IV, D ‐ II
- B.
A ‐ III, B ‐II , C ‐ I, D ‐ IV
- C.
A ‐ III, B ‐IV, C ‐ I, D ‐ II
- D.
A ‐ IV, B ‐III , C ‐ I, D ‐ II
Attempted by 40 students.
Show answer & explanation
Correct answer: C
Correct matching: A → Chomsky Normal Form; B → S-Grammar; C → Greibach Normal Form; D → Context-Sensitive Grammar
A: S → X Y; X → 0; Y → 1 — This matches Chomsky Normal Form because each production is either two nonterminals (S → X Y) or a single terminal (X → 0, Y → 1), which are exactly the CNF production types.
B: S → aS | bSS | c — This corresponds to the S-Grammar label in the question because its right-hand sides begin with a terminal and may be followed by one or more nonterminals (for example aS and bSS). These terminal-led, branching productions match the pattern designated by S-Grammar in the List II choices for this item (they are context-free, terminal-first productions suited to that classification).
C: S → AB; A → 0A | 1A | 0; B → 0A — This corresponds to Greibach Normal Form because the productions for the nonterminals A and B begin with a terminal followed (optionally) by nonterminals (for example A → 0A, 1A and B → 0A). In terms of derivations, these rules ensure that expansions ultimately produce strings that start with terminals, which is the key property of Greibach Normal Form used in this matching.
D: S → aAbc, Ab → bA, Ac → Bbcc, bB → Bb, aB → aa | aaA — This matches Context-Sensitive Grammar because several rules have left-hand sides that include surrounding symbols (e.g., Ab, Ac, bB, aB), so the applicability of a production depends on context. Such context-dependent replacements and length-preserving or length-increasing transformations are characteristic of context-sensitive grammars.