Match the following based on the language accepted by using brute force method of parsing.

List-I	List-II
a. $S \to aSa \mid aa$	I. $((2^n$ *3)-4); n > 1
b. $S \to aaSaa \mid aa$	II. $2^n$; n>=1
c. $S \to aaaSaaa \mid aa$	III. ((4*$2^n$)-6);n>=1
d. $S \to aaaaSaaaa \mid aa$	IV. $2^n$ - 2; n>= 2

Choose the correct answer from the options given below:

For $S \to aSa \mid aa$:

It generates strings:

$aa, aaaa, aaaaaa, \ldots$

So, length pattern is:

$2n$

Therefore,

a → II

For $S \to aaSaa \mid aa$:

It generates strings by adding two $a$'s on both sides.

So, it matches the given form IV.

Therefore,

b → IV

For $S \to aaaSaaa \mid aa$:

It generates lengths:

$2,8,14,20,\ldots$

This is:

$6n-4$

or

$((2n*3)-4)$

Therefore,

c → I

For $S \to aaaaSaaaa \mid aa$:

It generates lengths:

$2,10,18,26,\ldots$

This is:

$8n-6$

or

$((4*2n)-6)$

Therefore,

d → III

Correct matching:

a-II, b-IV, c-I, d-III