1
$\begingroup$

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

4

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

  • 0
    Well, I told you that it is the same as L1, and I told you what kind of language L1 is. Do you understand why L1 is context-free and not regular?2012-11-16
1

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