689 views

Given below are two statements:

Statement $I$: The problem “Is $L_1 \wedge L_2 = \phi$?” is undecidable for context sensitive languages $L_1$ and $L_2$

Statement $II$: The problem “Is $W \in L$?” is decidable for context sensitive language $L$. (where $W$ is a string).

In the light of the above statements, choose the correct answer from the options given below

1. Both Statement $I$ and Statement $II$ are true
2. Both Statement $I$ and Statement $II$ are false
3. Statement $I$ is correct but Statement $II$ is false
4. Statement $I$ is incorrect but Statement $II$ is true

1 comment

1. it is not re

Few Undecidable Problems for CFLs

L(G1) ∩ L(G2) = ∅  disjointness

L(G) = Σ*                universality

L(G)  Is Regular       regularity

L(G1) = L(G2)          equality ”

L(G) is ambiguous    ambiguity

The problem “Is W∈L?” is decidable for context sensitive language L. (where W is a string).

it is membership problem which is decidable for CFL

Hence both statements are true option A is correct ans

https://gatecse.in/grammar-decidable-and-undecidable-problems/