Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Consider the following grammar:

$S\to XY$

$X\to YaY\mid a$

$Y\to bbX$

Which of the following statements is/are true about the above grammar?

$(a)$ Strings produced by the grammar can have consecutive three $a$'s.

$(b)$ Every string produced by the grammar has alternate $a$ and $b$.

$(c)$ Every string produced by the grammar has at least two $a$'s.

$(d)$ Every string produced by the grammar has $b$'s in multiple of $2$.






Solution

Given grammar is

$S\to XY$

$X\to YaY\mid a$

$Y\to bbX$

Since $S\to XY$, the string contains one part from $X$ and one part from $Y$.

Now, $X$ can generate at least one $a$.

Also, $Y\to bbX$, so $Y$ also contains one $X$, which again gives at least one $a$.

Therefore, every string generated by $S$ has at least two $a$'s.

So, statement $(c)$ is true.

Also, every use of $Y$ contributes $bb$, that is $2$ occurrences of $b$.

So, the number of $b$'s is always in multiple of $2$.

Therefore, statement $(d)$ is true.

The grammar contains $bb$, so alternate $a$ and $b$ condition is false.

Also, consecutive three $a$'s are not necessarily produced.



Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...