Aspire's Library

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

Previous Year Question (PYQs)



Match List-I with List-II:
List-I List-II
(a) $\overline{L_3}\cup L_4$ (i) Context-free language
(b) $\overline{L_2}\cup L_3$ (ii) Recursively enumerable language
(c) $L_1^*\cap L_2$ (iii) Recursive language
where $L_1$: Regular language $L_2$: Context-free language $L_3$: Recursive language $L_4$: Recursively enumerable language Choose the correct option from those given below:





Solution

For $(a)$:

$L_3$ is a recursive language.

Complement of a recursive language is also recursive.

So,

$\overline{L_3}$ is recursive.

Also, $L_4$ is recursively enumerable.

Union of a recursive language and a recursively enumerable language is recursively enumerable.

Therefore,

$\overline{L_3}\cup L_4$ is recursively enumerable.

So,

$(a)\rightarrow(ii)$

For $(b)$:

$L_2$ is context-free language.

Every context-free language is recursive.

So, complement of $L_2$ is also recursive.

Also, $L_3$ is recursive.

Union of two recursive languages is recursive.

Therefore,

$\overline{L_2}\cup L_3$ is recursive.

So,

$(b)\rightarrow(iii)$

For $(c)$:

$L_1$ is regular.

Regular languages are closed under Kleene star.

So,

$L_1^*$ is regular.

Intersection of a regular language and a context-free language is context-free.

Therefore,

$L_1^*\cap L_2$ is context-free.

So,

$(c)\rightarrow(i)$

Hence, correct matching is

$(a)-(ii);\ (b)-(iii);\ (c)-(i)$



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