0
$\begingroup$

I know that if a language is regular then it is context free. and i know also that the class of regular languages are closed under intersection.

Now, Lets say we have two languages that are not context free call it L1 and L2 with alphabet{1}.

and we want to know if we have a language that is generated from the the intersection of L1 and L2 and is regular.

It would be nice if you give me example. Thanks

$\endgroup$
0
$\begingroup$

$L_1\cap L_2$ need not be regular: it won’t be regular if $L_1=L_2$, for instance. On the other hand, it can be regular. By Parikh’s theorem a language over the alphabet $\{1\}$ is context-free if and only it’s regular, so let $$L_1=\left\{1^{2^n}:n\in\Bbb Z^+\right\}$$ and $$L_2=\left\{1^{3^n}:n\in\Bbb Z^+\right\}\;;$$ these are not regular, so they’re not context-free, but their intersection is $\varnothing$, which is regular.

$\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.