Given below are two statements: L ∧ L = ϕ

Statement I : The problem "Is 1 2 ? " is L undecidable for context sensitive languages 1 L and 2. ∈

Statement II : The problem "Is W L?" is decidable W for context sensitive language L, (where is a string). In the light of the above statements, choose the correct answer from the options given below

1. ABoth Statement I and Statement II are true
2. BBoth Statement I and Statement II are false
3. CStatement I is correct but Statement II is false
4. DStatement I is incorrect but Statement II is true.

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. Both Statement I and Statement II are true

Explanation

Emptiness of the intersection of two context-sensitive languages is undecidable, while membership in a CSL is decidable (an LBA run is bounded).