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?
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.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.