Q57.Marks: +2.0UGC NET Paper 2: Computer Science 11 March 2023
Match the following based on the language accepted by using brute force method of parsing.
LIST - I
LIST - II
A.
S → aSa | aa
I.
((2n * 3) - 4) ; n ≥ 1
B.
S → aaSaa | aa
II.
2n ; n ≥ 1
C.
S → aaaSaaa | aa
III.
((4 * 2n) - 6) ; n ≥ 1
D.
S → aaaaSaaaa | aa
IV.
2n - 2 ; n ≥ 2
Choose the correct answer from the options given below:
1.A - IV, B - III, C - I, D - II
2.A - II, B - IV, C - I, D - III✓ Correct
3.A - I, B - IV, C - III, D - II
4.A - II, B - III, C - I, D - IV
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. 2n ; 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. 2n - 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. ((2n * 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 * 2n) - 6) ; n ≥ 1. Example: aa, aaaaaaaaaa, .....
