1
$\begingroup$

For two languages over the same alphabet that are not context-free, can their intersection be context-free, Or does at least one of them have to be context-free?

$\endgroup$
2
$\begingroup$

Let $L$ be an arbitrary language. Then $$ \{ 0x : x \in L \} \cap \{ 1x : x \in L \} = \emptyset. $$

$\endgroup$
2
$\begingroup$

The intersection of two CFL may or may not be a CFL. We can show that both possibilities exist. For example if both $L_1$ and $L_2$ are regular then $L_1∩ L_2$ is regular and therefore CF.

For intersection of non-context-free languages be context-free, you can assume that the intersection could be empty.

$\endgroup$

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.