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 production rules of grammer $G$:

$S\to AbB$

$A\to aAb\mid \lambda$

$B\to bB\mid \lambda$

Which of the following language $L$ is generated by grammer $G$?





Solution

Given,

$S\to AbB$

$A\to aAb\mid \lambda$

So, $A$ generates equal number of $a$ and $b$.

$A\Rightarrow a^n b^n$

Also,

$B\to bB\mid \lambda$

So, $B$ generates any number of $b$.

$B\Rightarrow b^k$

Now,

$S\Rightarrow AbB$

$S\Rightarrow a^n b^n b b^k$

$S\Rightarrow a^n b^{n+k+1}$

So, number of $b$ is always greater than number of $a$.

Therefore,

$L=\{a^n b^m:n\ge 0,m>n\}$


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