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 grammars:

$G_1:S\rightarrow aSb\mid bSa\mid aa$

$G_2:S\rightarrow aSb\mid bSa\mid SS\mid \lambda$

$G_3:S\rightarrow aSb\mid bSa\mid SS\mid a$

$G_4:S\rightarrow aSb\mid bSa\mid SS\mid SSS\mid \lambda$

Which of the following is correct w.r.t. the above grammars?






Solution

In $G_2$, productions are:

$S\rightarrow aSb\mid bSa\mid SS\mid \lambda$

In $G_4$, productions are:

$S\rightarrow aSb\mid bSa\mid SS\mid SSS\mid \lambda$

The only extra production in $G_4$ is:

$S\rightarrow SSS$

But this production is already possible using $S\rightarrow SS$ again and again.

For example:

$S\rightarrow SS\rightarrow SSS$

So, $SSS$ does not generate anything extra.

Hence, $G_2$ and $G_4$ generate the same language.



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...