Decidablity problem.

Question

Is L(G) subset of L(R) decidable ? Where G is CFG and R is regular grammar.

Problem can be reduced to checking if L(G) $\cap$ ( L(R))' = phi.

Now L(R)' is regular, so it also CFL and determining whether

L(G1) $\cap$ L(G2) = phi is known to be  undecidable where L(G1) and L(G2) are CFL's . So above problem should also be undecidable.

Where am I going wrong ?

Comments

CFL intersection CFL =  CSL

is it CSL or not is decidable

so should be decidable

i guess

---

L(G₁) ∩ L(G₂) = CFL ∩ Regular    // we know L ∩ Regular= would always be of type L

you should not upgrade regular to CFL when you have closure property for L ∩ regular too....

it's like CFL ∪ CFL = CSL ∪ CSL =CSL ....when CFL is closed under union , don't upgrade...

---

@Rupendra Choudhary, Thanks !

---

@Rupendra Choudhary, so the problem just reduces to checking if L(G) = phi and it is decidable right ?

---

CFL=∅ : problem of Emptiness for CFL , we have algorithm for it , so Decidable! Yes.

---

But the basic problem in the question is that it gives a way to slve a problem which happens to be undecidable. To make a problem undecidable there should be NO decidable ways. Just one undecidable way proves nothing. An application of first order logic and mostly mistaken by many and is the basis of reduction.

---

Some one please take an example and explain then it will be more clear.

---

Hello Sir

I'm not getting , which problem you're claiming UD?

inclusion of CFL into Regular is Decidable , and above we've proved it ...

did we go somewhere wrong ?

---

https://math.stackexchange.com/questions/70349/is-the-inclusion-of-a-regular-language-in-a-context-free-language-decidable

---

@Rupendra No, I was just answering the asked question and what exactly is the mistake there. What you told is correct.

---

@Arjun sir, I understand that to state a problem undecidable, there should not be any decidable way and one undecidable way(which I showed above) doesn't prove anything.

But if we go by the same argument then we can't say that problem is decidable because there is one undecidable way right ?

---

you meant to ask something else?

---

@Arjun sir, I didn't get you.

---

What you asked is trivial rt?

---

You said that I showed one way to solve the problem which is undecidable. So how is the problem decidable as I showed one undecidable way?

---

@Arjun Sir,  Also if possible, please check this question https://gateoverflow.in/153844/dma-cycle-stealing. I am still not sure of the answer.

---

@ xylene to prove it undecidable

each step that leads you there should be undecidable

in ur proof ..... the line CFL=∅ proves decidable

then u cannnot again proceed to undecidability

hope am clear enough

---

@Xylene yes, one undecidable way does not prove anything -- it can still be decidable or undecidable. But one decidable way is enough for decidability.

---

@Arjun, Ok sir, got it . Sir please answer this CO question https://gateoverflow.in/153844/dma-cycle-stealing

---

@Arjun sir, I have doubt about your statement "one decidable way is enough for proving decidability" . Consider another question like proving if L(R) is subset of L(G) is decidable or not ?

Now it is same as L(R) intersection L(G)' = phi .

Here CFL is not closed under complement, so it can be a CFL or not a CFL. If we consider it as CFL, then L(R) intersection CFL is a CFL and emptiness of CFL is decidable. So answer should be decidable as we have one way to prove it decidable but actually it's undecidable.

---

One way means one algorithm but should work for ALL INPUTS. You are showing an algorithm which works only for some inputs which is not a "one way" of proof.

---

@Arjun, Oh, I got it now. Can you please explain this compiler question in more detail ? https://gateoverflow.in/908/gate2003-18

---

How did u come up with this

"Problem can be reduced to checking if L(G) ∩( L(R))' = phi. " ?

---

@parshu

L(G) is a subset of L(R) which means it can have only the elemnts present in L(R)

L(R') gives elements which are not part of L(R) and these elements should not be present in L(G) since L(G) is a subset of L(R)

therefore L(G) ∩( L(R))' = phi. will confirm L(G) is a subset of L(R)

---

Thank you