0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Any subset of a finite set is finite.

The intersection of two sets is a subset of each.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Shubham Singh rawat Nov 3 '16 at 11:29
  • $\begingroup$ I suggest you review the material. If you have any further questions, ask them separately. Try harder answering your own questions. $\endgroup$ – Yuval Filmus Nov 3 '16 at 11:31
  • $\begingroup$ @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. $\endgroup$ – Rick Decker Nov 3 '16 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.