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 |
Show Answer With Best Explanation
| 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) |