Hey guys I got this question in my homework and I can't figure out what to do:
If the language $L$ is such that for every $CFL$ $L'$ , the language $L \cap L'$ is $CFL$, then $L$ is regular?
I sat down next to it few hours with no clue..
They gave us a huge hint it is not true. I think $L =\{a^nb^n\}$ when $\Sigma = \{a,b\}$ is a counterexample but I don't really know hot to prove it.
Don't know what tools can I use..
Let $L = \{a^n b^n\}$. Let us take some context free language $L'$ and prove that $L' \cap L$ is context free.
First, as $L \cap \{a^* b^*\} = L$ and $\{a^* b^*\}$ is regular, it's enough to consider cases when $L' \subseteq \{a^* b^*\}$.
Now, let us write grammar $G$ for $L'$ in Chomsky normal form. Now we will write another grammar $G_1$ that also generates $L'$.
For every nonterminal $X$ of $G$ we will add nonterminals $X_a$, $X_b$, $X$ to $G_1$ - intuitively $X_a$ will generate the words that can be generated from $X$ and consist only of letter $a$, $X_b$ similarly for $b$.
For each $X$ we add rules $X \to X_a$ and $X \to X_b$.
For each rule $X \to a$ we add rule $X_a \to a$, similarly for $b$. For each rule $X \to \varepsilon$ we add rule $X \to \varepsilon$.
For each rule $X \to YZ$ we add rules $X \to Y Z_b$, $X \to Y_a Z$ (intuitively, when we generate a word using $G$, we will either generate only $a$'s from $Y$, or only $b$'s from $Z$ - otherwise our word will not be in $a^*b^*$). We also add $X_a \to Y_a Z_a$ and $X_b \to Y_b Z_b$
Now, let us note that each $X_a$ generates a context-free language in single-letter alphabet $\{a\}$, and each $X_b$ generates a context-free language in single-letter alphabet $\{b\}$. Therefore, $X_a$ generates left-regular language, and $X_b$ generates right-regular language. So by adding new non-terminals we can create grammar $G_2$ that still generates $L'$, but in which all rules are of form $X \to Y Z_b$, $X \to Y_a Z$, $X_a \to a Y_a$, $X_b \to Y_b b$, $X_a \to \varepsilon$, $Y_b \to \varepsilon$.
Now let us finally define grammar $G_3$ that generates $L \cap L'$.
It will use $(X)$, $(X_a)$, $(X_b)$, $(X_a Y)$, $(Y Z_b)$, $(X_a Z_b)$, $(X_a Y Z_b)$ as nonterminals (is nonterminal for $G_3$ is one, two or three nonterminals of $G_2$). Intuitively, as we need to support number of $a$ and $b$ equal, we will can generate them in pairs and it will be enough for us to have at most $3$ nonterminals, with them been in the center of the string.
For each rule like $X \to Y Z_b$ of $G_2$ and for non-terminal of form $P_a$ of $G_2$ we add rule $(X) \to (Y Z_b)$, $(P_a X) \to (P_a Y Z_b)$. For each rule $X \to \varepsilon$ we add rule $(X) \to \varepsilon$.
For each rule $X_a \to X'_a$ and for each $U$ of kind $Y$ or $Y Z_b$ we add rule $(X_a U) \to (X'_aU)$. Similarly for rules $X_a \to \varepsilon$ and for $b$.
And now the most important part: for each pair of rules $X_a \to a X'_a$ and $Z_B \to Z'_b b$ and for each $Y$ we add rule $(X_a Y Z_b) \to a(X'_a Y Z'_b)b$. Intuitively, we write symbols only in pairs.
Then, if we had some generating path in $G_2$, we can transform it to generating path in $G_3$: if a non-terminal $X_a$ will produce at least one letter, we can produce it simultaneously with producing $b$ from some other non-terminal.