Discussion
Which of the following decision problems are undecidable?
I. Given NFAs \(N_{1}\) and \(N_{2}\), is \(L(N_{1}) \cap L(N_{2}) = \Phi\)?
II. Given a CFG \(G = (N, \Sigma, P, S)\) and a string \(x \in \Sigma^{*}\), does \(x \in L(G)\)?
III. Given CFGs \(G_{1}\) and \(G_{2}\), is \(L(G_{1}) = L(G_{2})\)?
IV. Given a TM \(M\), is \(L(M) = \Phi\)?
Answer: C
Problems III and IV are undecidable, so the answer is III and IV only.
- I is decidable: build the product automaton for \(L(N_{1}) \cap L(N_{2})\) and check whether any accepting state is reachable.
- II is decidable: membership in a context-free language is decided by the CYK algorithm.
- III is undecidable: equivalence of two context-free grammars cannot be decided in general.
- IV is undecidable: emptiness of a Turing machine's language is a non-trivial property of recursively enumerable languages, undecidable by Rice's theorem.
Any option containing I or II includes a decidable problem.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development