The Gateway to Computer Science Excellence
+34 votes

Which of the following is/are undecidable?

  1. $G$ is a CFG. Is $L(G) = \phi$?
  2. $G$ is a CFG. Is $L(G) = \Sigma^*$?
  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)$?
  1. 3 only      
  2. 3 and 4 only      
  3. 1, 2 and 3 only      
  4. 2 and 3 only
in Theory of Computation by Veteran
edited by | 3.3k views
Regarding the option - Given a CFG. Is it empty or not?

Since the Language is (<G>| G is a CFG and L(G) is empty). We can find one TM which accepts an empty string and one which doesn't. Then by Rice's theorem, this property is non trivial and thus undecidable for Recursively Enumerable languages which involve CFLs.
What am I missing here?
@Arjun Sir

Can you give some intuition regarding why 2 is undecidable?

2 Answers

+32 votes
Best answer

It will be D.

  1. First is Emptiness for CFG.
  2. Second is everything for CFG.
  3. Third is Regularity for REC
  4. Fourth is equivalence for regular.
by Boss
edited by
why second is undecidable pls explain?
@madhab we know that emptiness problem is decidable on cfl and we also know that CFL is not closed under complement operation so we cant say about its complement that is Σ*
parallely u can see that regular and dcfl are closed under complement and on regular and dcfl emptiness problem is decidable and also these are closed under complement so completeness problem is also decidable on regular an dcfl but not on cfl

@Arjun SIR,

What is this everything for CFG. ? Can u pls explain what is option B means ?



everything means E according to him ; i think so.

L(G)=E? this is decidable upto DCFL. not for rest wrt to chomsky hierarchy.

If i check that start symbol is "useful" for CFG, will this check emptiness of CFG ?
Please, some one explain to me why option B is undecidable because CFG is closed under emptiness? and Σ∗ is countable so simply it will be Decidable.

Third is Regularity for REC. Why is it REC and not RE asTM deals with RE and always halting TM deals with REC @Gate Keeda


Brij Mohan Gupta

in second option it is universality problem ,it is undecidable for cfl but decidable for dcfl.



Regularity problem is undecidable for both REC & RE

thank you.
Can anyone explain why option 2 is undecidable and what does option 2 means?
Arent 1st , 2nd and 4th Decidable

3rd is undecidable why is answer d?
+6 votes
There is an algorithm to check whether the given CFG is empty, finite or infinite and also to
convert NFA to DFA hence 1 and 4 are decidable
by Active

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,876 answers
118,119 users