Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Given below are two statements:
Statement I: The problem "Is $L_1\cap 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:
Statement I: The problem "Is $L_1\cap 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:
Solution
Statement I is true.For context sensitive languages, the emptiness problem is undecidable.
Since context sensitive languages are closed under intersection, checking whether:
$L_1\cap L_2=\phi$
is also undecidable.
So, Statement I is true.
Statement II is also true.
Membership problem for context sensitive languages is decidable.
This is because context sensitive languages are accepted by Linear Bounded Automata, and for a fixed input there are only finitely many configurations.
Therefore, we can decide whether $W\in L$ or not.
So, both statements are true.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
