Given below are two statements: Statement 𝐼: The problem “Is 𝐿1∧𝐿2=𝜙?” is…
2020
Given below are two statements:
Statement 𝐼: The problem “Is 𝐿1∧𝐿2=𝜙?” is undecidable for context sensitive languages 𝐿1 and 𝐿2
Statement 𝐼𝐼: The problem “Is 𝑊∈𝐿?” is decidable for context sensitive language 𝐿. (where 𝑊 is a string).
In the light of the above statements, choose the correct answer from the options given below
- A.
Both Statement 𝐼 and Statement 𝐼𝐼 are true
- B.
Both Statement 𝐼 and Statement 𝐼𝐼 are false
- C.
Statement 𝐼 is correct but Statement 𝐼𝐼 is false
- D.
Statement 𝐼 is incorrect but Statement 𝐼𝐼 is true
Attempted by 24 students.
Show answer & explanation
Correct answer: A
Final answer: Both statements are true.
Statement I: The problem “Is the intersection of two context-sensitive languages empty?” is undecidable. Reason: The emptiness problem for context-sensitive languages (languages accepted by linear bounded automata) is undecidable, and since context-sensitive languages are closed under intersection, asking whether L1 ∩ L2 = ∅ remains an undecidable question.
Statement II: The membership problem “Is a given string w in a given context-sensitive language L?” is decidable. Reason: Context-sensitive languages are exactly those accepted by (nondeterministic) linear bounded automata, which always run within space linearly bounded by the input length and therefore decide membership in finite (PSPACE) time. Membership for context-sensitive languages is decidable (and in fact PSPACE-complete).
Therefore both statements are true.
A video solution is available for this question — log in and enroll to watch it.