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?
- 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 60 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.