retagged by
16,653 views
38 votes
38 votes

Consider the following problems. $L(G)$ denotes the language generated by a grammar $G$. L(M) denotes the language accepted by a machine $M$.

  1. For an unrestricted grammar $G$ and a string $w$, whether $w  \in  L(G)$
  2. Given a Turing machine $M$, whether $L(M)$ is regular
  3. Given two grammar$G_1$ and $G_2$, whether $L(G_1) = L(G_2)$
  4. Given an NFA $N$, whether there is a deterministic PDA $P$ such that $N$ and $P$ accept the same language

Which one of the following statement is correct?

  1. Only I and II are undecidable
  2. Only II is undecidable
  3. Only II and IV are undecidable
  4. Only I, II and III are undecidable
retagged by

3 Answers

Best answer
89 votes
89 votes

$4^{\text{th}}$ Statement : Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language

Is Decidable because We can Always say that There will definitely be a DPDA (and for that matter PDA too) which will accept the same language that NFA N is accepting. But Careful, Saying that (From other answers for this question)   "PDA (accepting CFL)  having more power than NFA (accepting regular) so we can decide whether both will accept the same language or not." is WRONG. 

"Given a <PDA> P and a NFA N, Deciding Whether they both accept the same language or not" is Undecidable. " 

"Given a <DPDA> D and a NFA N, Deciding Whether they both accept the same language or not" is Decidable.  "


$3^{\text{rd}}$ Option (Third Statement ) :  Given two grammars G1 and G2, whether L(G1) = L(G2) 

is Undecidable. Because When nothing is mentioned about the type of the Grammar, It, by default, should be taken as A Valid Grammar i.e. Type 0 Grammar which itself covers All the Grammars.  

So, Now the given problem is nothing but  "Equivalence of two RE Grammars i.e. Equality of Two RE languages" Problem.  Which is Undecidable. 


Many students are confusing this statement with that of "Propositional Logic" statements. Which is not the case here. Let me elaborate : We all know that Equivalence of RE languages is Undecidable...But One could argue that Some RE languages are Regular also and for Regular languages, Equivalence Problem is Decidable.  So Saying that "Equivalence of RE languages is Undecidable" would seem wrong.  But We Know that  It is NOT. 

And This is because When we say "Decidable", It means that there is an Algorithm (Automation) to solve that problem and If that Problem is really decidable then You should be able to give an Algorithm for that, which for All Valid Instances should Halt and Say Yes/No. 


"Equality" and "Equivalence" are two different things. Equality of Grammars (Type 0-3 Grammars) is Decidable, But Equivalence is NOT Because Equivalence of Two Grammars is a relation defined by "Equality of Their Corresponding Languages" , Which is Undecidable for Type-0 Grammars.


From the Comments on the question "In order to prove a statement wrong, we need only one counter example.Statement was " $L1 = L2$ is undecidable". It should not be true as it is decidable in case of regular languages."" ... 

See, "In order to prove a statement wrong, we need only one counter example" is a Generalized statement (NOT A THEOREM or A Proven Fact) usually used in Logic.. But "Generalization" is the Enemy/opposite of "Specification / particularization / Specific ". 

Correct Answer: $D$

edited by
18 votes
18 votes
Membership of Unrestricted grammar is undecidable.
Turing machine may not halt so undecidable.
Two grammars are equal is undecidable

PDA (accepting CFLs)  having more power than NFA (accepting regular) so we can decide whether both will accept the same language or not.
edited by
6 votes
6 votes
Unrestricted grammar generate RE for which membership is not defined i.e. undecidable.

Regularity problem for TM is undecidable

Equivalence of Two grammar is undecidable.

D is answer
Answer:

Related questions

27 votes
27 votes
6 answers
1
gatecse asked Feb 14, 2018
11,318 views
The set of all recursively enumerable languages is:closed under complementationclosed under intersectiona subset of the set of all recursive languagesan uncountable set
34 votes
34 votes
5 answers
4