Match the following based on the language accepted by using brute force method…
2022
Match the following based on the language accepted by using brute force method of parsing.
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
Attempted by 131 students.
Show answer & explanation
Correct answer: B
Solution: Derive the length formula for each grammar by examining the base string and how many a's each recursive step adds.
Grammar A: S → a S a | aa. Base string 'aa' has length 2. Each recursive application adds one 'a' at the left and one at the right (2 characters). Therefore lengths are 2, 4, 6, ... which is length = 2n for n ≥ 1.
Grammar B: S → aa S aa | aa. Base 'aa' has length 2. Each recursive step adds two 'a's on the left and two on the right (4 characters). Thus lengths are 2, 6, 10, ... which can be written as length = 4n − 2 (re-indexing n appropriately).
Grammar C: S → aaa S aaa | aa. Base 'aa' length 2. Each recursive step adds three 'a's on each side (6 characters). Therefore lengths are 2, 8, 14, ... which follow length = 6n − 4 for n ≥ 1.
Grammar D: S → aaaa S aaaa | aa. Base 'aa' length 2. Each recursive step adds four 'a's on each side (8 characters). Hence lengths are 2, 10, 18, ... following length = 8n − 6 for n ≥ 1.
Therefore the correct mapping of each grammar to its length formula is:
A → lengths 2n, n ≥ 1
B → lengths 4n − 2 (sequence 2, 6, 10, ...)
C → lengths 6n − 4 (sequence 2, 8, 14, ...)
D → lengths 8n − 6 (sequence 2, 10, 18, ...)
This corresponds to the given correct matching: A → 2n; n ≥ 1, B → 4n − 2, C → 6n − 4, D → 8n − 6.