GATE CSE 2006 | Question: 33

Question

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a  recursively enumerable, but not recursive, language. Which one of the following statements is false?

• A. $L_1 \cap L_2$  is a deterministic CFL
• B. $L_3 \cap L_1$  is recursive
• C. $L_1 \cup L_2$  is context free
• D. $L_1 \cap L_2 \cap L_3$  is recursively enumerable

Comments

$L_1$ is regular $\implies$ ( it is recursive AND it is also recursively enumerable.) i.e. $REC\ and \ RE$

$L_3$  is not recursive AND it is recursively enumerable. i.e. $(\sim REC)\ and \ RE$

$L_1 \cap L_3 = $ common part of both $L_1$ and $L_3 = RE$

---

Apparently this is a paradox, viewing it from set theory point of view seems correct and if viewed by definitions also it seems correct, set theory is providing wrong answer, why ?

My thought is that both explanations are correct, however the important point is RE but no REC by saying this we have actually restricted ourself to the outermost track(acc to set diagram), now there is no way we can move inwards to reach inner RL circle.

So we must expand the properties of RL to matchup with the outer track.

Once we do that both theories align and we have a track which is RECURSIVE ENUMERABLE but not RECURSIVE, hence the options B becomes false.

 

Option D however tells the same thing but with correct explanation hence it is correct. Thanks @Satbir sir

---

there is another simple way to look at option b:

Let $L_1 = \Sigma^*$ (which is Regular). Then $L_3 \cap L_1 = L_3 \cap \Sigma^* = L_3$.

Since $L_3$ is given as not recursive, $L_3 \cap L_1$ is not necessarily recursive so option B$\implies$ FALSE.

Answer 1

• A. True : DCFL are closed under Intersection with Regular Languages
• B. False : $L_1$ is recursive hence also decidable, $L_3$ is RE but not Recursive hence it is undecidable. Intersection of Recursive language and Recursive Enumerable language is Recursive Enumerable language.
• C. True : $L_1$ is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
• D. True : $L_1$ is regular hence also RE; $L_2$ is DCFL hence also RE; RE languages are closed under Intersection

Comments

Counter example for option B:

let $L_{1}$ be $(a,b)^{*}$  (regular) and $L_{2}$ be some recursively enumerable language over (a,b).

Now $L_{1}$$\bigcap$ $L_{2}$ = $L_{2}$ , which is recursively enumberable and not recursive.

I am not very sure about the approach, please correct me if I am wrong.

---

for option C,

if L1 is everything, and L2 is a^n b^n

Then L1 U  L2 = everything = regular

But regular languages are context free.

So option C is correct

---

@sanjaysharmarose

Very good question. When we view regular language as DCFL, then intersection with another DCFL may or may not be DCFL (we cannot comment)

But, we have additional information regarding the language (it is Regular), we know that regular intersection with DCFL is DCFL 

Answer 2

L1∩L2 is a deterministic CFL because intersection of any lang. with regular is closed.

L3∩L1 is recursive is False because it should be RE {recursive enumerable not recursive}

L1∪L2 is context free is true, because every DCFL is CFL.

L1∩L2∩L3 is recursively enumerable is true.

Comments

can you please explain 4th option ?

---

Recursive enumerable is higher set, so, L1∩L2∩L3 whatever lang. may come , we can say it is recursively enumerable.

---

• From Option A, $(L_1 \cap L_2)$ is a DCFL, which means it is also a Recursive language.

• Every Recursive language is also an RE language.

• Since RE languages are closed under intersection, the intersection of $(L_1 \cap L_2)$ with $L_3$ produces an RE language $\implies$ TRUE.

Answer 3

We can understand option B by thinking of constructing a TM for the language $L_1 \cap L_2$ and then analyzing if it is a halting TM or not.

---

Basic Info - 

• We know $L_1$ is regular, hence recursive (decidable), and has a halting TM. Let that TM be $TM_1$.  A halting TM is one that halts and accepts for all strings that are in the language, and halts and rejects for all strings that are not in the language.

 

• We know $L_2$ is RE but not REC, hence semi-decidable, and has a simple TM. Let that TM be $TM_2$. A simple TM is one that halts and accepts for all strings that are in the language, but may either halt and reject or loop infinitely for strings that are not in the language

 

---

Construction of TM $R$:

We now want to construct a TM $R$ for the language $L_1 \cap L_2$ (i.e., the set of strings $x$ that are in both $L_1$ and $L_2$).

TM $R$ is a combination of $TM_1$ and $TM_2$. On input string $x$, it follows this algorithm:

1. Run the halting TM $TM_1$ (decider) of $L_1$ on $x$. (Since $TM_1$ decides $L_1$, this step always halts.)

2. Check $TM_1$ result:

   • If $TM_1$ rejects (i.e., $x \notin L_1$), then reject (halt and reject).
   • If $TM_1$ accepts (i.e., $x \in L_1$), proceed to Step 3.

3. Run $TM_2$ on $x$:

   • If $TM_2$ accepts, then $R$ accepts.
   • If $TM_2$ rejects (i.e., $x \notin L_2$), then reject (halt and reject).
   • If $TM_2$ loops (because $x \notin L_2$), $R$ loops.

---

Analyse $R$:

• If $x \in L_1 \cap L_2$, then $R$ would halt and accept.

 

• But if $x \notin L_1 \cap L_2$, then $R$ might halt and reject or it might go into an infinite loop because of Step 3.3 of the algorithm.

 

---

 

Hence, we will surely be able to halt and accept for all the strings in the language, but we might go into an infinite loop for strings that are not in the language. This behavior confirms that $R$ is a semi-decider for $L_1 \cap L_2$.

$$\text{Therefore, } L_1 \cap L_2 \text{ is Recursively Enumerable (RE).}$$