engineering recuitment GATE CSE 2023-24 Test Series Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Consider the following problems. L(𝐺) denotes the language generated by a grammar 𝐺. L(𝑀) denotes the language accepted by a machine 𝑀.
Which one of the following statements is/are undecidable?
1
Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.
2
For an unrestricted grammar 𝐺 and a string 𝑤, whether 𝑤 ∈ (𝐺)
3
Given a Turing machine M, whether L(M) is regular
4
Given two grammars 𝐺1 and 𝐺2, whether (𝐺1) = (𝐺2)