Take the 2-minute tour ×

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

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


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?

share|improve this question

2 Answers 2

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

share|improve this answer
My second question is whether L1-L3 is regular or CFL language? –  Sudhir Nov 14 '12 at 16:06
The set difference of L1 and L2 language. –  Sudhir Nov 14 '12 at 17:17
Yes, sorry, I just realised that from the edited title of your question, which I hadn't noticed before. –  Tara B Nov 14 '12 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? –  Tara B Nov 15 '12 at 9:16
Could you please clarify me that L1-L3 is CFG or Regular language? –  Sudhir Nov 16 '12 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.

share|improve this answer

Your Answer


