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

Step 1: Regular languages under intersection (A)
Regular languages are closed under all Boolean operations. Given DFAs $M_1$ for $L_1$ and $M_2$ for $L_2$, construct the product automaton $M$ whose state set is $Q_1 \times Q_2$, start state $(q_{1,0}, q_{2,0})$, transition $\delta\big((p,q),a\big)=(\delta_1(p,a),\delta_2(q,a))$, and accepting set $F_1 \times F_2$. Then $L(M)=L_1 \cap L_2$.
\Rightarrow\; (A) True.
Step 2: Context-free languages under intersection (B)
CFLs are not closed under intersection in general (they are closed under intersection with regular languages, but not with arbitrary CFLs). A standard counterexample is:
\[ L_1=\{\,a^i b^i c^k \mid i,k \ge 0\,\},\qquad L_2=\{\,a^k b^i c^i \mid i,k \ge 0\,\}, \]
both of which are context-free. Their intersection is
\[ L_1 \cap L_2=\{\,a^n b^n c^n \mid n \ge 0\,\}, \]
which is a classic non-CFL.
\Rightarrow\; (B) False.
Step 3: Recursive (decidable) languages under intersection (C)
If $L_1$ and $L_2$ are recursive (decidable), there exist Turing machines $D_1,D_2$ that halt on all inputs and decide membership for $L_1,L_2$ respectively. Build a decider $D$ for $L_1 \cap L_2$ that runs $D_1$ and $D_2$ sequentially (or in parallel) and accepts iff both accept; otherwise rejects. Since both $D_1$ and $D_2$ halt on every input, $D$ also halts on every input.
\Rightarrow\; (C) True.
Step 4: Recursively enumerable languages under intersection (D)
If $L_1$ and $L_2$ are recursively enumerable (RE), there exist recognizers $R_1,R_2$ that accept exactly the strings in $L_1,L_2$ (they may loop forever on strings not in the language). To recognize $L_1 \cap L_2$, dovetail: simulate one step of $R_1$, then one step of $R_2$, and so on; accept the input iff both $R_1$ and $R_2$ eventually accept. If the input is not in the intersection, at least one recognizer will never accept, so our machine never accepts—exactly the RE behavior.
\Rightarrow\; (D) True.
\[ \boxed{\text{Correct statements: (A), (C), and (D).}} \]