$L_1=\{a^ncb^n\} \cup \{a^mdb^{2m}\}$

$L_2 = \{ a^{2n}cb^{2m+1} \} \cup \{a^{2m+1}db^{2n}\}$

This is my exam question on two days ago. Option is:

$1)$ $L_1 \cap L_2$ is Regular Language.

$2)$ $L_1 \cap L_2$ is not a Context free.

$3)$ $L_1 \cap L_2$ is Non deterministic Context Free.

$4)$ $L_1 \cap L_2$ is deterministic Context Free and not Regular.

My teacher gives a short solution answer and $(4)$ is correct choice. anyone could describe me why? how we can inference this difficult question?


A slightly different approach to the problem is to let $$\begin{align} X_1 &= \{a^ncb^n\mid n\ge 0\}\\ X_2 &= \{a^{2n}cb^{2m+1}\mid n, m\ge 0\}\\ Y_1 &= \{a^mdb^{2m}\mid m\ge 0\}\\ Y_2 &= \{a^{2m+1}db^{2n}\mid n, m\ge 0\} \end{align}$$ so $$ L_1 = X_1\cup Y_1\quad\text{and}\quad L_2=X_2\cup Y_2 $$ and thus $$ L_1\cap L_2=(X_1\cap X_2)\cup(X_1\cap Y_2)\cup(X_2\cap Y_1)\cup(Y_1\cap Y_2) $$ Now observe that $X_i\cap Y_j=\varnothing$, since every string in $X_i$ contains $c$ and no string in $Y_j$ does, so $L_1\cap L_2=(X_1\cap X_2)\cup(Y_1\cap Y_2)$.

Further, it's not hard to show that $X_1\cap X_2=\varnothing$, so $$\begin{align} L_1\cap L_2&=Y_1\cap Y_2\\ &=\{a^idb^j\mid i=2m+1\land j=2i\}\\ &=\{a^{2m+1}db^n\}\cap\{a^jdb^{2j}\}\\ &=Z_1\cap Z_2 \end{align}$$ Clearly $Z_1$ is regular and $Z_2$ is a DCFL so their intersection is a DCFL. Finally, an easy pumping lemma proof establishes that $Z_1\cap Z_2$ isn't regular, so answer (4) is correct, as expected.

  • $\begingroup$ Your answer is so nice, but one problem, you are so expert but I'm not, you say "an easy pumping lemma proof " can you show me to learn? $\endgroup$ – Moji Moji Aug 3 '16 at 19:15
  • $\begingroup$ @MojiMoji. It usually takes me an hour or so to cover the pumping lemma for regular languages, so any tutorial would be much longer than would be appropriate here. I'd suggest that you find a proof that the language $a^nb^n$ isn't regular (almost any text will have it) and modify it slightly for the problem at hand. $\endgroup$ – Rick Decker Aug 3 '16 at 19:34
  • $\begingroup$ Owww, Ok, I‌ get it. Would you please let me to study. thanks so much. $\endgroup$ – Moji Moji Aug 3 '16 at 19:35
  • 2
    $\begingroup$ @MojiMoji: There’s a pumping lemma proof here that $\{a^nb^n:n\ge 0\}$ isn’t regular. $\endgroup$ – Brian M. Scott Aug 3 '16 at 19:51
  • 1
    $\begingroup$ Wow @BrianM.Scott Thanks, I read in 30 hours on it, but couldn't generalize it on my specific question, Would you please show it on my specific question?. I need a great answer (also this answer is), but I means even it maybe long, but it's valuable to learn others some long answer or some proof that show creativity and not directly deduced in some question. $\endgroup$ – Moji Moji Aug 3 '16 at 19:58

First realize that $L_1$ is context free and $L_2$ is regular. Can you see why? Once you realize this, just use simple closure properties (a quick wikipedia search of context free languages will help you build a closure chart). Since all four answers list intersections, you know that a context free language intersected with a regular language is in fact context free (and not regular in this case), so answer 4) is the correct answer.

EDIT: $L_1$ is context-free and you can show it by coming up with a CFG for the language. For $L_1$, a grammar could be

$S \rightarrow C|D\\ C\rightarrow c | aCb\\ D\rightarrow d | aDbb$

I assume $n\ge 0$ and $m \ge 0$.

For $L_2$, you can come up with an NFA for $L_3 = \{a^{2n}cb^{2m+1}\}$ and $L_4 = \{a^{2m+1}db^{2n}\}$ and connect them with epsilon transitions.

  • $\begingroup$ The intersection of a context-free and a regular language may be regular. This one isn't, but it will take an explicit argument to show that. $\endgroup$ – Henning Makholm Aug 3 '16 at 16:31
  • $\begingroup$ Good catch, I meant in this specific case. I'll edit $\endgroup$ – m1cky22 Aug 3 '16 at 16:31
  • $\begingroup$ @HenningMakholm you are right, this is make this as a challenging question. $\endgroup$ – Moji Moji Aug 3 '16 at 16:33
  • $\begingroup$ The most challenge is why $L_1$ is CF and $L_2$ is Regular :). another tips of your solution is so nice. $\endgroup$ – Moji Moji Aug 3 '16 at 16:36
  • $\begingroup$ $L_2$ is regular, and you can come up with a simple NFA to prove it (draw two NFAs for each sublanguage in the union, and connect them with epsilon transitions). $L_1$ being a CFG is a bit more complicated to write in a comment so I'll edit my answer $\endgroup$ – m1cky22 Aug 3 '16 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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