4th 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. "**

*3rd 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 " L_{1 }= L_{2} 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 ". **