# Intersection with a finite set

If we have a language $F$ and a regular language $D$ (a finite set) then can we say anything about the intersection of $D$ and $F$? Will the intersection of the languages be finite or regular?

This question arises from another question which says

Show that if $L$ is not a CFL and $F$ is finite then $L - F$ is not a CFL.

Now $L = (L - F) ∪ ( L ∩ F)$.

Now if I am able to prove that $L ∩ F$ is finite or regular than I can arrive at a contradiction as follows:

If $L ∩ F$ is finite or regular then union with $L-F$ will be a CFL, therefore $L$ will be a CFL, which is a contradiction.

But my problem is assuming anything about $L ∩ F$.

What will be the properties of this intersection?

There is no need to consider the intersection $L \cap F$. If $F$ is finite, then so is $L \cap F$, but that is not a useful fact here.

Insteed, one should proceed by contradiction. Suppose $L \setminus F$ were a context-free language. Then there exists a context-free grammar $G_1 = (V_1,\Sigma,R_1,S_1)$ such that $L(G_1) = L \setminus F$. But since $F$ is finite, then $F$ is trivially a context-free language. Let $G_2 = (V_2,\Sigma,R_2,S_2)$ be a context-free grammar such that $L(G_2) = F$.

But then $G = (V,\Sigma,R,S)$ where $S \notin V_1 \cup V_2$ and

$$V = V_1 \cup V_2 \cup \{ S \}$$ $$R = R_1 \cup R_2 \cup \{ S \rightarrow S_1, S \rightarrow S_2 \}$$

is a context-free grammar such that $L(G) = L$. This is a contradiction.

Any subset of a finite set is finite.

The intersection of two sets is a subset of each.

• once we have arrived at the point that L∩F is finite is my proof correctly structured? Can we safely assume ( L−F )∪( L∩F ) is a CFL? what should be the reasoning behind this? Union of a CFL with a finite language isn't guaranteed to be a CFL right? – Shubham Singh rawat Nov 3 '16 at 11:29
• I suggest you review the material. If you have any further questions, ask them separately. Try harder answering your own questions. – Yuval Filmus Nov 3 '16 at 11:31
• @ShubhamSinghrawat. If $L$ is a CFL and $F$ is finite, then $L-F$ is a CFL. To show this, you can use the fact that while CFLs aren't closed under intersection, the intersection of $L$ with any regular language is a CFL. Then, since $L-F=L\cap\overline{F}$ ($\overline{F}$ denotes the complement of $F$) and $F$ is finite, then $F$ is regular, so $\overline{F}$ is also regular, and so $L$ intersected with $\overline{F}$ is a CFL. – Rick Decker Nov 3 '16 at 13:34