...
Software-Engineering
November 11, 2023
Algorithm-Paradigms
November 11, 2023
Software-Engineering
November 11, 2023
Algorithm-Paradigms
November 11, 2023

Question 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.
A
3 only
B
3 and 4 only
C
1, 2 and 3 only
D
2 and 3 only
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x