Match List I with List II List I A. S → aSa | aa B. S → aaSaa | aa C. S →…
2022
Match List I with List II
List I
A. S → aSa | aa
B. S → aaSaa | aa
C. S → aaaSaaa | aa
D. S → aaaaSaaaa | aa
List II
I. ((2ⁿ 3) - 4), n ≥ 1
II. 2ⁿ, n ≥ 1
III. ((4 2ⁿ) - 6), n ≥ 1
IV. 2ⁿ - 2, n ≥ 1
Choose the correct answer from the options given below:
- A.
A-(IV), B-(III), C-(I), D-(II)
- B.
A-(II), B-(IV), C-(I), D-(III)
- C.
A-(I), B-(IV), C-(III), D-(II)
- D.
A-(II), B-(III), C-(I), D-(IV)
- E.
None
Attempted by 25 students.
Show answer & explanation
Correct answer: E
Analyze the length of strings generated by each grammar in List I.
Grammar A (S → aSa | aa) generates strings of length 2, 4, 6... following the linear formula L(n) = 2n.
Grammars B, C, and D similarly generate linear sequences (e.g., 4n-2, 6n-4) because they add a fixed number of characters per recursive step.
List II contains exponential formulas (2^n) or invalid negative values, which do not match the linear growth of any grammar.
Therefore, no valid matches exist between List I and List II.
A video solution is available for this question — log in and enroll to watch it.