Software-Engineering
November 11, 2023Algorithm-Paradigms
November 11, 2023Question 8779 – Theory-of-Computation
Which of the following is/are undecidable?
-
1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
Correct Answer: D
Question 57 Explanation:
Emptiness problem for context free language is decidable, so 1 is decidable.
Completeness problem for context free language is undecidable, so 2 is undecidable.
Whether language generated by a Turing machine is regular is also undecidable, so 3 is undecidable.
Language accepted by an NFA and by a DFA is equivalent is decidable, so 4 is decidable.
Completeness problem for context free language is undecidable, so 2 is undecidable.
Whether language generated by a Turing machine is regular is also undecidable, so 3 is undecidable.
Language accepted by an NFA and by a DFA is equivalent is decidable, so 4 is decidable.
3 only
3 and 4 only
1, 2 and 3 only
2 and 3 only
Subscribe
Login
0 Comments