Discussion
Consider the following problems. \(L(G)\) denotes the language generated by a grammar \(G\). \(L(M)\) denotes the language accepted by a machine \(M\).
(I) For an unrestricted grammar \(G\) and a string \(w\), whether \(w \in L(G)\)
(II) Given a Turing machine \(M\), whether \(L(M)\) is regular
(III) Given two grammars \(G_{1}\) and \(G_{2}\), whether \(L(G_{1}) = L(G_{2})\)
(IV) Given an NFA \(N\), whether there is a deterministic PDA \(P\) such that \(N\) and \(P\) accept the same language.
Which one of the following statements is correct?
Answer: D
The correct statement is Only I, II and III are undecidable.
- I: unrestricted grammars generate exactly the recursively enumerable languages, so their membership problem is as hard as the halting problem: undecidable.
- II: being regular is a non-trivial property of the language of a Turing machine, so by Rice's theorem it is undecidable.
- III: equivalence of two grammars is undecidable already for context-free grammars, so it is undecidable for grammars in general.
- IV: an NFA accepts a regular language, and every regular language is accepted by a deterministic PDA (a DFA that ignores its stack). The answer is always yes, so the problem is trivially decidable.
The options leaving out I, II or III, or listing IV as undecidable, are therefore wrong.
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