Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Let

$L_1=\{0^n1^n0^m\mid n\ge 1,\ m\ge 1\}$

$L_2=\{0^n1^m0^m\mid n\ge 1,\ m\ge 1\}$

$L_3=\{0^n1^n0^n\mid n\ge 1\}$

Which of the following are correct statements?

A. $L_3=L_1\cap L_2$

B. $L_1$ and $L_2$ are context free languages but $L_3$ is not a context free language

C. $L_1$ and $L_2$ are not context free languages but $L_3$ is a context free language

D. $L_1$ is a subset of $L_3$

Choose the correct answer from the options given below:





Solution

$L_1$ has equal number of first $0$'s and $1$'s, so it is CFL.

$L_2$ has equal number of $1$'s and last $0$'s, so it is also CFL.

Now,

$L_1=\{0^n1^n0^m\}$

$L_2=\{0^n1^m0^m\}$

In $L_1\cap L_2$, number of first $0$'s $=$ number of $1$'s and number of $1$'s $=$ number of last $0$'s.

So,

$L_1\cap L_2=\{0^n1^n0^n\}=L_3$

Thus, statement A is true.

$L_3=\{0^n1^n0^n\mid n\ge 1\}$ is not context free language.

So, statement B is true.

Statement C is false because $L_1$ and $L_2$ are CFL.

Statement D is false because $L_1$ contains strings like $0011000$, which are not in $L_3$.


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