Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$\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|cite|improve this question

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|cite|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|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.