regular languages ,context free grammer.

76 Views Asked by At

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

1

There are 1 best solutions below

0
On

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