1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Here is a more interesting variant. $\endgroup$ Nov 1, 2020 at 19:28

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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