Which of the following decision problems are undecidable? I. Given NFAs…
GATE · 2016 · CS · Set 1 · Computer Science & IT
Which of the following decision problems are undecidable?
I. Given NFAs and , is L(N1) ∩ L(N2) = ∅ ?
II. Given a CFG and a string , does ?
III. Given CFGs and , is ?
IV. Given a TM , is ?
- A.
I and IV only
- B.
II and III only
- C.
III and IV only
- D.
II and IV only
Attempted by 110 students.
Sign up free to check your answer
Sign up freeLoading lesson…