UGC NET Computer Science December 2019 | Question 100

Question 100

---

Consider the following language families :
L₁ = The context - free languages
L₂ = The context - sensitive languages
L₃ = The recursively enumerable languages
L₄ = The recursive languages
Which one of the following options is correct?

1. (1) L₁ ⊆ L₂ ⊆ L₃ ⊆ L₄
2. (2) L₂ ⊆ L₁ ⊆ L₃ ⊆ L₄
3. (3) L₁ ⊆ L₂ ⊆ L₄ ⊆ L₃
4. (4) L₂ ⊆ L₁ ⊆ L₄ ⊆ L₃

Answer : (3) L1 ⊆ L2 ⊆ L4 ⊆ L3

Explanation

Every regular language is context-free, every context-free language is context-sensitive, every context-sensitive language is recursive and every recursive language is recursively enumerable. These are all proper inclusions, meaning that there exist recursively enumerable languages that are not context-sensitive, context-sensitive languages that are not context-free and context-free languages that are not regular.

Theory of Computation - Chomsky Hierarchy

Reference : Theory of Computation - Chomsky Hierarchy

So, option 3 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 99	UGC NET CS December 2019 - Question 101