GATE CSE 2018 | Question: 36

Question

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?

• A. Only I and II are undecidable
• B. Only II is undecidable
• C. Only II and IV are undecidable
• D. Only I, II and III are undecidable

Comments

is it $D$?

---

Hint: Use Rice's Theorem

---

https://gatecse.in/grammar-decidable-and-undecidable-problems/

---

NOTE : $II$ is present in all options, so we can ignore it in exam.

Answer 1

$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$

Comments

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

Let me share my approach towards making this problem Decidable.

Enumerate all the strings of countable($\left \{ a,b \right \}^{*}$), and note down the strings which are accepted by PDA P(Membership algorithm for PDA is decidable).

Say the Language accepted by PDA P is L.

Then check whether each string in L is accepted by NFA N.

If all the strings in L are accepted by NFA N, then L(P) = L(N).

 

As of now, I don’t see any glitch in this algorithm, I guess it seems to be decidable.

Any comments on this are highly appreciated.

 

---

@Deepak Poonia Sir can you pls explain why is it:-

"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.  "

---

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

For those who are not getting this-

We can convert nfa to dfa. We can also convert dfa to dpda by simply not using the stack. And we know that the equality problem of dcfl is decidable. 

Answer 2

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.

Comments

Yes, it should be A

---

If there arises one case in which it is undecidable, then the problem statement as a whole is considered undecidable. This is quite similar to logical proposition, the statement must be true for all cases.

---

In order to prove a statement wrong, we need only one counter example.

statement was " L₁=L₂ is undecidable". It should not be true as it is decidable in case of regular languages. The question was not about that given statement is valid or satisfiable or if the given statement is tautology or contradiction. May be you are right but this statement should not be true.

Answer 3

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

Comments

How equivalence of two grammar is undecidable?

Grammar can be regular also.So, in that case it is decidable.

https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html

---

I believe equivalency of grammar is decidable but for language it is not

---

but incase of cfg it is undecidable