# How to deduce Intersection and Difference of these languages?

$\mathcal{L1}=\{a^nb^n c^m d^m\;|\;m,n>=1\}$

$\mathcal{L2}=\{a^nb^n \;|\;n>=1\}$

$\mathcal{L3}={(a+b)^*}$

How to deduce the Intersection of $\mathcal{L1}$ and $\mathcal{L2}$ is CFG or Regular?

Also $\mathcal{L1}$-$\mathcal{L3}$ is CFG or Regular language? Can anyone clarify both the questions?

## 2 Answers

The first and second languages are both context-free but not regular (the second one is a very standard example of a non-regular language). The intersection of these two languages is empty, since there is no word which is both of the form $a^nb^nc^md^m$ and $a^nb^n$ with $m\geq 1$. The empty language is regular (just use an automaton with no accept states).

As for the second question: well, none of the words in $\cal{L}1$ are in $\cal{L}3$, since words in $\cal{L}1$ all contain $c$s and $d$s as well as $a$s and $b$s. So $\cal{L}1 - \cal{L}3 = \cal{L}1$.

• My second question is whether L1-L3 is regular or CFL language? Commented Nov 14, 2012 at 16:06
• The set difference of L1 and L2 language. Commented Nov 14, 2012 at 17:17
• Yes, sorry, I just realised that from the edited title of your question, which I hadn't noticed before. Commented Nov 14, 2012 at 17:19
• Could you please let me know whether I've answered your question or whether there's anything you still don't understand? Commented Nov 15, 2012 at 9:16
• Could you please clarify me that L1-L3 is CFG or Regular language? Commented Nov 16, 2012 at 9:23

$L_1−L_3=L_1$ and $L_1$ is a context-free language. If you know what PDA accepts $L_2$, then you can find a PDA for $L_1$ easily, since $L_1$ is concatenation of $L_2$ and $L={{c^n d^n: n>=1}$. PDA for L would be similar to the one for $L_2$, you just need to replace a by c and b by d.