The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 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
asked in Theory of Computation by Veteran (355k points)
edited by | 2k 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

+26 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.
answered by Boss (19.7k points)
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?
+5 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
answered by Active (2.1k points)

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

37,941 questions
45,453 answers
48,210 users