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

Consider the ...

Question

Consider the following problems:
(a) L is a context sensitive languages (CSL), complement of L is of same type.
(b) Let $L_{1}$ and $L_{2}$ is CSL, intersection of $L_{1}$ and $L_{2}$ is empty or not.
(c) Finiteness problem in CFGs.
(d) Emptiness problem for CFGs
Which of the following problwms is/are decidable?

Open in App

Solution

(a) L is a context sensitive languages (CSL), complement of L is of same type.

(c) Finiteness problem in CFGs.

(d) Emptiness problem for CFGs

Suggest Corrections

Similar questions

L_{1} L_{2}

L_{1} \cup L_{2}

_{1}

L_{1} - R

L_{1} \cap L_{2}

L_{1} a n d L_{2}

L_{1}

L_{2}

_{1}

L_{1}

_{2}

L_{2}

_{1}

_{1} \cup L_{2}

L_{1}

L_{2}

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} and L 2

L_{1}

L_{2}

D C F L .

L_{3} = (L_{1} \cap L_{2}^{*})^{'}

L_{3}

Join BYJU'S Learning Program