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 language $L={a^n b^{n-3}\mid n>2}$ on $\Sigma={a,b}$. Which one of the following grammars generates the language $L$?





Solution

Given language is:

$L={a^n b^{n-3}\mid n>2}$

When $n=3$:

$a^3b^0=aaa$

When $n=4$:

$a^4b^1=aaaab$

When $n=5$:

$a^5b^2=aaaaabb$

So, every string starts with at least three $a$ symbols.

After that, for every extra $a$, one $b$ is added at the end.

Grammar:

$S\rightarrow aaaA$

$A\rightarrow aAb\mid \lambda$

If $A\rightarrow \lambda$, then string is:

$aaa$

If $A\rightarrow aAb$, then it generates:

$aaaab,\ aaaaabb,\ldots$

So, this grammar generates $a^n b^{n-3}$ for $n>2$.



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