Solution

The correct answer is A - II, B - IV, C - I, D - III

Key Points

• List I describes grammar productions while List II describes the lengths of the strings generated by those grammars. Looking at the grammar productions, they generate strings of specific lengths by inserting 'a's at specific positions. Let's interpret each grammar:

​​

• A. (S → aSa | aa), everytime you recursively descend, you add an 'a' on both sides of the string. This step doubles the length, starting from the base string 'aa' which has length of 2. Therefore, it matches with II. 2ⁿ ; n ≥ 1. Example: aa, aaaa, aaaaaa, .....

 

• B. (S → aaSaa | aa), you add 'aa' on both sides upon each recursive descend, effectively adding 4 to the length each iteration, starting from the base string 'aa' which has length of 2. So it generates strings with lengths of (4n - 2) for n ≥ 1 this matches with IV. 2ⁿ - 2 ; n ≥ 2. Example: aa, aaaaaa,aaaaaaa, ....

 

• C. (S → aaaSaaa | aa), each recursive step adds 'aaa' on both sides, essentially adding 6 to the length on each recursion, starting from 'aa' with length of 2. So it generates strings of lengths (6n - 4) for n ≥ 1, this matches with I. ((2ⁿ * 3) - 4) ; n ≥ 1. Example: aa, aaaaaaaa, aaaaaaaaaaaaaa, ......

 

• D. (S → aaaaSaaaa | aa), each recursion results in 'aaaa' on either side of the string, leading to an increase of 8 characters, starting from 'aa' which has length of 2. So it generates strings of lengths (8n - 6) for n ≥ 1, due to 4 base characters added on each side, this matches with III. ((4 * 2ⁿ) - 6) ; n ≥ 1. Example: aa, aaaaaaaaaa, .....