Consider the following problems. ๐ฟ(๐บ) denotes the language generated by aโฆ
2018
Consider the following problems. ๐ฟ(๐บ) denotes the language generated by a grammar ๐บ. ๐ฟ(๐) denotes the language accepted by a machine ๐.
(I) For an unrestricted grammar ๐บ and a string ๐ค, whether ๐ค โ ๐ฟ(๐บ)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars ๐บ1 and ๐บ2, whether ๐ฟ(๐บ1) = ๐ฟ(๐บ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. Only I, II and III are undecidable โ Answer: Only I, II and III are undecidable. Explanation: I. Membership for an unrestricted (type-0) grammar is undecidable: type-0 grammars generateโฆ
- A.
Only I and II are undecidable
- B.
Only III is undecidable
- C.
Only II and IV are undecidable
- D.
Only I, II and III are undecidable
Attempted by 69 students.
Show answer & explanation
Correct answer: D
Answer: Only I, II and III are undecidable.
Explanation:
I. Membership for an unrestricted (type-0) grammar is undecidable: type-0 grammars generate recursively enumerable languages, and deciding whether a given string belongs to such a language is equivalent to the Turing machine acceptance problem (undecidable, though semi-decidable).
II. Given a Turing machine M, deciding whether L(M) is regular is undecidable: regularity is a nontrivial property of the language recognized by M, so Rice's theorem implies this problem is undecidable.
III. Equivalence of two grammars (whether L(G1) = L(G2)) is undecidable for unrestricted grammars (and is undecidable for several other broad grammar classes as well).
IV. For an NFA N, there always exists a deterministic PDA accepting the same language because every regular language is deterministic context-free (a DFA is a special case of a DPDA). Therefore this question is decidable (the answer is always yes).
A video solution is available for this question โ log in and enroll to watch it.