Consider the following problems. ๐ฟ(๐บ) denotes the language generated by aโฆ
GATE ยท 2018 ยท CS ยท Computer Science & IT
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 93 students.
Sign up free to check your answer
Sign up freeLoading lessonโฆ