You visited us 2 times! Enjoying our articles? Unlock Full Access!

Closure properties of CFL Part - 2

Consider the ...

Question

Consider the two languages $L_{1} and L 2$ where $L_{1}$ is regular and $L_{2}$ is $D C F L .$ Then the language $L_{3} = (L_{1} \cap L_{2}^{*})^{'}$ is/are true about $L_{3}$ ?

Recursively enumerable

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

C F G

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C S L

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Recursive

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Open in App

Solution

The correct option is D Recursive
$L_{3} = (L_{1} \cap L_{2} ⋆)^{'} = (D C F L^{⋆} \cap Regular)$

= (Regular $\cap C F L$ )
$= (C F L)^{'} = C S L$ (using the closure property)

Suggest Corrections

Similar questions

L_{1} : R e g u l a r, L_{2} : C o n t e x t - f r e e, L_{3} : R e c u r s i v e, L_{4} : R e c u r s i v e l y e n u m e r a b l e .

_{3} \cup L_{4}

_{2} \cup L_{3}

_{1} \cap L_{2}

L_{1} \cup_{2}

L_{1} = 0^{*} 1^{*}, L_{2} = 1^{*} 0^{*}, L_{3} = (0 + 1)^{*} and L_{4} = 0^{*} 1^{*} 0^{*} .

L = (L_{1} \cap L_{2}) - (L_{3} \cap L_{4})

0^{p} 1^{q} | p, q ϵ N

0^{p} 1^{q} | p, q ϵ N

0^{p} 1^{q} 0^{r} | p, q, r ϵ N

L_{1} L_{2}

L_{1} \cup L_{2}

_{1}

L_{1} - R

L_{1} \cap L_{2}

0^{i} 1^{j} | i \neq j

0^{i} 1^{j} i = j

0^{i} 1^{j} | i = 2 j + 1

0^{i} 1^{j} | i \neq 2 j

Join BYJU'S Learning Program