Decidable undecidable – Theory of Computing
|Question 1 UGC NET June-2020 |
Given below are two statements:
Statement I: The problem “Is L1 ∧ L2=Ø?” is undecidable for context sensitive languages L1 and L2.
Statement II: The problem “Is W ∈ 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
|A – Both Statement I and Statement II are true|
|B – Both Statement I and Statement II are false|
|C – Statement I is correct but Statement II is false|
|D – Statement I is incorrect but Statement II is true|
|Question 2 UGC NET June-2020 |
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems:
A) Is L(G1)=L(G2)?
B) Is L(G2)≤L(G1)?
C) Is L(G1)=R?
Which of the problems are undecidable?
Choose the correct answer from the options given below:
|A – (A) only|
|B – (B) only|
|C – (A) and (B) only|
|D – (A), (B) and (C)|