Question

Which of the following statements is/are CORRECT?

• A. The intersection of two regular languages is regular.
• B. The intersection of two context-free languages is context-free.
• C. The intersection of two recursive languages is recursive.
• D. The intersection of two recursively enumerable languages is recursively enumerable.

Hint:

Remember the closure table: Regular $\Rightarrow$ closed under $\cap$; CFLs are not closed under $\cap$ (but are closed under $\cap$ with Regular); Recursive (decidable) sets are closed under all Boolean operations; RE sets are closed under $\cup$ and $\cap$ (via dovetailing recognizers) but not under complement.

Answer 1

The Correct Option is A

Let's examine each statement to determine which are correct:

1. The intersection of two regular languages is regular.
2. The intersection of two context-free languages is context-free.
3. The intersection of two recursive languages is recursive.
4. The intersection of two recursively enumerable languages is recursively enumerable.

Analysis:

1. The intersection of two regular languages is regular:

   Regular languages are closed under intersection. This means that if you have two regular languages, their intersection is also a regular language. This follows from the properties of regular languages and can be proven using finite automata. Therefore, this statement is correct.

2. The intersection of two context-free languages is context-free:

   Context-free languages are not closed under intersection. While there are some specific cases where the intersection of context-free languages could be context-free, in general, it is not guaranteed. Therefore, this statement is incorrect.

3. The intersection of two recursive languages is recursive:

   Recursive languages are closed under intersection. This means the intersection of two recursive languages is always a recursive language. Hence, this statement is correct.

4. The intersection of two recursively enumerable languages is recursively enumerable:

   Recursively enumerable languages are not closed under intersection. This means that even if each of the two languages is recursively enumerable, their intersection might not be. Therefore, this statement is incorrect.

Conclusion:

The correct answer is: "The intersection of two regular languages is regular." and "The intersection of two recursive languages is recursive."