Question 16
Which CFG problem is undecidable?
Detailed Solution
Ambiguity of a general CFG is undecidable.
✓ Saved
GATE CSE Turing Machines, RE Languages & Undecidability – TOC Practice Test | Set 1
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 17
What is the decidability status of the Post Correspondence Problem?
Detailed Solution
PCP is a classical undecidable problem.
✓ Saved
Question 18
If A $\le B$ and B is decidable, what follows about A?
Detailed Solution
A decision procedure for B can be combined with the reduction from A to B.
✓ Saved
Question 19
If an undecidable problem A reduces to B, what follows about B?
Detailed Solution
If B were decidable, the reduction would give a decider for A.
✓ Saved
Question 20
Which statement about the halting language L_HALT is correct?
Detailed Solution
A TM can recognize L_HALT by simulating M on w, but no TM decides it.
✓ Saved