UGC NET CSE | December 2019 | Part 2 | Question: 50

Question

Consider the following language families:

$L_1 \equiv$ The context-free languages

$L_2 \equiv$ The context-sensitive languages

$L_3 \equiv$ The recursively enumerable languages

$L_4 \equiv$ The recursive languages

Which one of the following options is correct?

• A. $L_1 \subseteq L_2 \subseteq L_3 \subseteq L_4$
• B. $L_2 \subseteq L_1 \subseteq L_3 \subseteq L_4$
• C. $L_1 \subseteq L_2 \subseteq L_4 \subseteq L_3$
• D. $L_2 \subseteq L_1 \subseteq L_4 \subseteq L_3$

Answer 1

According to Chomsky hierarchy:

• Every Context-free language is Context-sensitive language.
• Every Context-sensitive language is a recursive language
• Every recursive language is recursively enumerable language.

That is $\text{CFL$\subseteq$CSL$\subseteq$REC$\subseteq$REL}=L_1\subseteq L_2 \subseteq L_4 \subseteq L_3$

Option $(C)$ is correct.

Ref: Chomsky- hierarchy

Answer 2

set of finite languages $\subseteq$ set of regular languages $\subseteq$ set of context free languages$\subseteq$set of context sensitive languages$\subseteq$set of recursive languages$\subseteq$set of recursively enumerable languages

So option 3 is the correct answer.