The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+9 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$.

- For an unrestricted grammar $G$ and a string $w$, whether $w \: \epsilon \: L(G)$
- Given a Turing machine $M$, whether $L(M)$ is regular
- Given two grammar$G_1$ and $G_2$, whether $L(G_1) = L(G_2)$
- 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?

- Only I and II are undecidable
- Only II is undecidable
- Only II and IV are undecidable
- Only I, II and III are undecidable

+21 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 " 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"

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.

+4

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

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

Given an NFA

N, whether there is a deterministic PDAPsuch thatNandPaccept 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.

0

@Shaik Masthan @Deepakk Poonia (Dee)

What if we see 4th statement like this

Given an NFA

N, whether there is a deterministic PDAPsuch thatNandPaccept 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) ??

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

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

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

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.

+2

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

+3

But G_{1} and G_{2} 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?

+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 " L_{1}=L_{2} 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

Regularity problem for TM is undecidable

Equivalence of Two grammar is undecidable.

D is answer

+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

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 5.9k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 588
- Exam Queries 568
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,071 questions

53,206 answers

184,562 comments

70,424 users