Let \(L(R)\) be the language represented by regular expression \(R\). Let…
GATE · 2017 · CS · Set 2 · Computer Science & IT
Let be the language represented by regular expression . Let be the language generated by a context free grammar . Let be the language accepted by a Turing machine . Which of the following decision problems are undecidable?
I. Given a regular expression and a string , is ?
II. Given a context-free grammar , is
III. Given a context-free grammar , is for some alphabet ?
IV. Given a Turing machine and a string , is ?
- A.
I and IV only
- B.
II and III only
- C.
II, III and IV only
- D.
III and IV only
Attempted by 94 students.
Sign up free to check your answer
Sign up freeLoading lesson…