Aspire's Library
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
| 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:
Solution
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
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
