0
$\begingroup$

how can i prove the following statement :

1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL .

so i want to know what is the method to prove it ?

I'm not sure, but can i use a PDA and DFA or something else ?


so i tried the following :

$L_2$ is regular and thus is $\overline{\rm L_2}$ also regular.

$L_1 \cap \overline{\rm L_2}$ is CFL $\iff$ $L_1 \cap \overline{\rm L_2}$ is recognized by a PDA.

$M1=(Z_1,\Sigma,\Gamma,\delta_1,z_{01},$#$,E_1)$ is a PDA for $L_1$

$M_2=(Z_1,\Sigma,\delta_2,z_{02},E_2)$ is a DFA for $\overline{\rm L_2}$

$M^{'}$=($Z_1$x$Z_2$,$\Sigma,\Gamma,\delta^{''},(z_{01},z_{02}),$#$,E_1$x$E_2)$ , so that $M^{'}$=$M_1\cap M_2$

but how should i define $\delta{'' ?}$

Many Thanks

$\endgroup$
  • $\begingroup$ What closure properties do you know? Intersection of a CFL and a regular language? $\endgroup$ – Hendrik Jan Jul 3 '17 at 21:24
  • $\begingroup$ from what i studied i know that CFLs are closed under the following properties : the union the concatenation the Kleene star but not under Intersection $\endgroup$ – proless8 Jul 3 '17 at 21:28
  • $\begingroup$ but for a CFL and a regular language i don't know any $\endgroup$ – proless8 Jul 3 '17 at 21:28
  • 1
    $\begingroup$ I suggest spending some more time with this question. It is within your capabilities. $\endgroup$ – Yuval Filmus Jul 3 '17 at 21:30
  • $\begingroup$ i was able to conclude that $L_1$ \ $L_2$ = $L_1 \cap \overline{\rm L_2}$ is this correct , but still i can't understand exacly how to start i have been trying since yesterday $\endgroup$ – proless8 Jul 3 '17 at 21:34

Your Answer

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

Browse other questions tagged or ask your own question.