+12 votes
3.6k views

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 \: \epsilon \: 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

edited | 3.6k views
+2
is it $D$?
0
Hint: Use Rice's Theorem

## 3 Answers

+26 votes
Best answer

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

by Boss (25.1k points)
edited
0
Must be made Best Answer.
0
Nice Explanation!!
0

Hi, @Deepakk Poonia (Dee),

Could you please define "Equality" of grammars slightly more clearly? That would be very helpful.

Also, I need to confirm that it is due to Non-determinism of NPDA that made u say--"Given a <PDA> P and a NFA N, Deciding Whether they both accept the same language or not" is Undecidable. "

Thanks.

+6

For any RE language, there could exist infinite Grammars which generate that language. These all Grammars are different but they generate same language, that's why we say that they are equivalent. Equivalence is a relation which is based on some condition. In Study of Grammars, for a set of all Type-0 Grammars, Equivalence is defined as "Generation  of same language". Saying that Two Grammars are Equal and Saying that Two grammars are Equivalent is Different. Two different Grammars could generate the same language and it can be realized intuitively. You must have seen many Grammars generating same language. We call such Grammars Equivalent, Not Equal.

Deciding whether two Grammars are Equal or Not is very much Decidable...You can simply write a Algorithm of "Text Matching".

For instance, 4 = 4, But 4$\neq$1, But 4 and 1 could be Equivalent, if Equivalence is defined as "Mod 3" relation.

Answering the Other doubt, For CFL's it is Undecidable and for DCFL's it is Decidable.

0
Thanks :)
0

what my view on 4$^{th}$ statement is :

Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language

Convert NFA into DFA

$\color{red}{L(DFA) - L(DPDA)} = \color{green}{L(DPDA) - L(DFA)} = ∅$

i) L(DPDA) - L(DFA) = L(DPDA) ∩ L'(DFA) ===> DPDA intersection with Regular = DPDA

So, it is turned into the resultant as L(DPDA) = ∅ ? ===> which is decidable.

Note that DPDA can be converted into DCFL

ii) L(DFA) - L(DPDA) = L(DFA) ∩ L'(DPDA) ===> DPDA intersection with Regular = DPDA

So, it is turned into the resultant as L(DPDA) = ∅ ? ===> which is decidable.

∴ Given statement is decidable.

if it is PDA, instead of DPDA, then

ii) L(DFA) - L(DPDA) = L(DFA) ∩ L'(DPDA) ===> DPDA intersection with Regular = DPDA

So, it is turned into the resultant as L(DPDA) = ∅ ? ===> which is decidable.

ii) L(DFA) - L(PDA) = L(DFA) ∩ L'(PDA) ===> Recursive intersection with Regular = Recursive

So, it is turned into the resultant as L(Recursive) = ∅ ? ===> which is Un-decidable.

+2

What if we see 4th statement like this

Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language

Let NFA is N and DPDA is D

we have to decide L(N) ==  L(D) ??

L(N) is regular hence DCFL and L(D) is already DCFL so it is Equality of DCFLs problem which is Decidable

If it is NPDA ,

It will be Equalty of NCFLs which is Undecidable

-------------------------------------------------------------------------------------------------------------------------------------------

0
yes it is right !

but what happen, if it is ⊆ instead of = symbol, between them as per your approach ?

i mean, we have to decide L(N) ⊆  L(D) ??
0
L(N) is regular hence DCFL and L(D) is already DCFL,

If it is  ⊆  ..then It will be DCFL ⊆  DCFL ...which is undecidable according that table..
+1

decide L(N) ⊆  L(D) ??

but actually it is decidable !

0
@ shaik.....i think bcz DCFL satisfy

only prefix property accepted by empty stack in DCFL

and it is deterministic also.
0
I didn't get you elaborate for which statement you are explained?
0
"decide L(N) ⊆  L(D) ??"
0

only prefix property accepted by empty stack in DCFL

and it is deterministic also.

from these statements how you are going to decide,  L(N) ⊆  L(D) ?

+14 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.
by Veteran (60k points)
edited
+2

In case of Regular grammer (Type 3), wheather L1=L2 is decidable. So we cannot say that statement iii) is undecidable. so Option A) should be correct. Please correct me If I am wrong.

+5
Yes but G1 or G2 may not be Regular or DCFL.
In that case, it would be Undecidable.
+3

But G1 and G2 can be regular (in which it is decidable to check their equality) so how can we generalize the statement that it is undecidable because in one case(Regular) it is decidable?

+1
Yes, it should be A
+3
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.
0

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

+5 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
by Veteran (62.2k points)
+2

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

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

+9 votes
5 answers
1
+13 votes
2 answers
2
+12 votes
3 answers
4
+7 votes
4 answers
5
+7 votes
10 answers
6
+7 votes
6 answers
7