Undecidable Problems MCQ Quiz in తెలుగు - Objective Question with Answer for Undecidable Problems - ముఫ్త్ [PDF] డౌన్లోడ్ కరెన్
Last updated on Apr 7, 2025
Latest Undecidable Problems MCQ Objective Questions
Top Undecidable Problems MCQ Objective Questions
Undecidable Problems Question 1:
Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let L = { < M > | M is a Turing machine that accepts a string of length 2014 }. Then, L is
Answer (Detailed Solution Below)
Undecidable Problems Question 1 Detailed Solution
Concept:
Recursive Enumerable (RE):
Using rice’s theorem we can find out whether the problem is decidable or undecidable.
Explanation:
There will be 2 cases for the string of length 2014:
Case 1: String is accepted by Turing machine.
Case 2: It will halt on non-final state or go on a loop.
This is nothing but definition of recursive enumerable.
Rice theorem 1: Any non-trivial property of L(TM) is undecidable.
Given problem is a non-trivial property as there are TM whose language contains such a string and there are TM whose language doesn’t have such a string so given problem is undecidable.
Undecidable Problems Question 2:
Which of the following are undecidable?
P1: The language generated by some CFG contains any words of length less than some given number n.
P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3: Any given CFG is ambiguous or not.
P4: For any given CFG G, to determine whether epsilon belongs to L(G).Answer (Detailed Solution Below)
Undecidable Problems Question 2 Detailed Solution
Concept:
Decidable problems: If there is an algorithm to solve a problem then that problem is known as decidable.
Undecidable problem: These problems do not have an algorithm that gives correct output infinite.
Explanation:
1) The language generated by some CFG contains any words of length less than some given number n.
This is a decidable problem. The language contains words of length less than some number n. It means strings are of finite length. Finiteness is a decidable problem.
2) Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements.
One language is CFL and the other is regular. L1 ∩ L2 is decidable.
3) Any given CFG is ambiguous or not.
Ambiguity problem for any language is undecidable. For ambiguous problems, there does not exist any finite time algorithm that can solve it.
4) For any given CFG G, to determine whether epsilon belongs to L(G)
It means context-free language is empty. Emptiness property of context free languages in undecidable.Undecidable Problems Question 3:
If L(S) be context sensitive language, then which of the following is/are true?
I. \(\overline {L\left( S \right)}\) is context sensitive language
II. For a context-sensitive language L(S) and a string x, whether x ϵ L(M).
III. L(S1) - L(S2) is context-sensitive language
IV. L(S) is finite or notAnswer (Detailed Solution Below)
Undecidable Problems Question 3 Detailed Solution
- Context-sensitive language are closed under complementation and set difference and hence option I and III are decidable
- Membership problem for a context sensitive language is decidable.
- Finiteness problem for a context sensitive language is undecidable.
Undecidable Problems Question 4:
The post correspondence solution
Answer (Detailed Solution Below)
Undecidable Problems Question 4 Detailed Solution
| M | abb | aa | aaa |
| N | bba | aaa | aa |
Here,
Undecidable Problems Question 5:
Let P be a push down Automata which of the following is /are decidable for L(P)?
I. Checking whether it is empty
II. Checking whether it is Regular
III. Checking whether it is FiniteAnswer (Detailed Solution Below)
Undecidable Problems Question 5 Detailed Solution
Undecidable Problems Question 6:
If a problem P1 is reducible to problem P2 and P1 is undecidable then P2 is:
Answer (Detailed Solution Below)
Undecidable
Undecidable Problems Question 6 Detailed Solution
Language A is reducible to language B (represented as A ≤ B) if there exists a function which will convert A to B.
Rule:
If A ≤ B and if A is undecidable, B is also undecidable.