Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is:
The intersection of a context-free language and a regular language always results in a context free language, but does this also mean that if I have a language L1 and a regular language L2 that when L1 intersected with L2 is context free that L1 is also context free?
Your clam is false even in the special case where $L_1 \cap L_2$ is regular.
To construct a counterexample let $L_1$ be a language that is not context free (e.g., $L_1 = \{a^n b^n c^n: n \ge 0\}$) and pick $L_2 =\emptyset$ (other choices for $L_2$ work too).
Both $L_2 = \emptyset$ and $L_1 \cap L_2 = \emptyset$ are regular (and hence also context-free), but $L_1$ was chosen as a non-context free language.
