Question

If \( L_i \) is the set of languages of type \( i \) for \( i = 0, 1, 2 \) or 3. Then, as per Chomsky hierarchy, arrange the given set of four languages in order from subset to superset, from left to right. 

(A) \( L_3 \) 
(B) \( L_2 \) 
(C) \( L_1 \) 
(D) \( L_0 \) 
Choose the correct answer from the options given below:

• A. A, B, C, D
• B. A, C, D, B
• C. B, A, D, C
• D. C, B, D, A

Hint:

In Chomsky's hierarchy, remember that \( L_3 \) (Regular languages) is the simplest, and each subsequent type includes the previous one.

Answer 1

The Correct Option is A

 

Step 1: Understanding the Chomsky Hierarchy. 
In the Chomsky hierarchy, languages are classified into four types based on their complexity: - Type 0: Recursively enumerable languages 

- Type 1: Context-sensitive languages 

- Type 2: Context-free languages 

- Type 3: Regular languages 

The hierarchy is ordered as follows, with each type being a subset of the next: \[ L_3 \subseteq L_2 \subseteq L_1 \subseteq L_0 \]

Step 2: Applying the Order. 
From the Chomsky hierarchy, we know that regular languages (\( L_3 \)) are the simplest and are a subset of context-free languages (\( L_2 \)), which in turn are a subset of context-sensitive languages (\( L_1 \)), and finally, recursively enumerable languages (\( L_0 \)) are the most general.

Step 3: Conclusion. 
Therefore, the correct order from subset to superset is \( L_3 \), \( L_2 \), \( L_1 \), and \( L_0 \), which corresponds to option (1) A, B, C, D.