CFG and Regularity of Two Language?

99 Views Asked by At

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

2

There are 2 best solutions below

6
On

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.

7
On

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.