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 statements with respect to the language $L={a^n b^n\mid n\ge 0}$

$S_1:L^2$ is context free language

$S_2:L^k$ is context-free language for any given $k\ge 1$

$S_3:\overline{L}$ and $L^*$ are context free languages

Which one of the following is correct?






Solution

Given language:

$L={a^n b^n\mid n\ge 0}$

This is a context free language.

Now check each statement.

For $S_1$:

$L^2=L\cdot L$

Context free languages are closed under concatenation.

So, $L^2$ is also context free.

Hence, $S_1$ is true.

For $S_2$:

$L^k$ means concatenation of $L$ with itself $k$ times.

For any fixed $k\ge 1$, context free languages are closed under finite concatenation.

So, $L^k$ is context free.

Hence, $S_2$ is true.

For $S_3$:

$L^*$ is context free because context free languages are closed under Kleene star.

Also, for this specific language $L={a^n b^n\mid n\ge 0}$, its complement $\overline{L}$ is also context free.

So, $\overline{L}$ and $L^*$ both are context free languages.

Hence, $S_3$ is true.

Therefore, all three statements $S_1,\ S_2$ and $S_3$ are correct.



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