Question

Which of the following is/are undecidable?
1. G is CFG Is L(G)=$\Phi$?
2.G is CFG Is L(G)=${\sum }^{\ast }$?
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)?

Answer 1

1. G is CFG.Is L(G) =$\Phi$?
This is the emptiness problem of CFLs which is decidable.
2. G is CFG,Is L(G)=${\sum }^{\ast }$.
This is the Kleene closedness problem of CFLs which is undecidable.
3. M is turning machine.Is L(M) regular.
This is the regularity problem of REs which is undecidable.
4. A is a DFA and N is NFA.Is L(A)=L(N)?.
This is the equivalence problem of regular languages which is decidable.
So, only 2 and 3 are undecidable.