TIFR CSE 2010 | Part B | Question: 25

Question

Which of the following problems is decidable? (Here, CFG means context free grammar and CFL means context free language.)

• A. Given a CFG $G$, find whether $L(G) = R$, where $R$ is regular set.
• B. Given a CFG $G$, find whether $L(G) = \{\}$.
• C. Find whether the intersection of two CFLs is empty.
• D. Find whether the complement of CFL is a CFL.
• E. Find whether CFG $G_1$ and CFG $G_2$ generate the same language, i.e, $L\left (G_1 \right ) = L\left (G_2 \right)$.

Answer 1

• A. We don't have any standard algorithm to change $CFG$ into $CFL$ 
  from a given $CFG$ deciding a language is finite is decidable but regular its undecidable (Ref: http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems)  
• B. From a given given CFG we can determine the $CFL$ and $CFL$ emptiness is Decidable.
• C. Intersection of two CFL is undecidable coz it is not closed under intersection.
• D. $CFL$ is not closed under Complement so its undecidable.
• E. $CFL$ is not closed under equivalence so it is undecidable to compare $2$ language.

Therefore, B is decidable and A,C,D and E are undecidable.

Comments

@sachin CFG are not decidable under intersection, e.g G1 = {a^n b^n c^m | n,m >=0} intersection {a^m b^n c^n| n,m >=0 } result will be {a^n b^n c^n | n>=0} this string are not decidable for any size. if size is not fixed.

---

@sushmita Can you please explain how..?

---

I think D is decidable. 

Proof-

For testing a language to be CFL you need to check if it can be accepted by push down automata.

So we can conclude that----  “Whether a given any language is Context free language or not..?”   is Decidable.  The given language may be CSL --In this case also the above is Decidable.

 

Now, Let X be a CFL. Then complement of X is a CSL for sure.

Let complement of X is L (a CSL).

As we know -- “Whether any given language is Context free language or not?”   is Decidable  ,    so “whether L is CFL or not?”  is decidable.

 

Which implies  “whether complement of a CFL is CFL or not?”  is decidable.

 

What is wrong in this?

Answer 2

Ans : B

By decision property of cfg

1.does L(G) is empty (Decidable)

2.does L(G) is finite(Decidable)

3.does L(G) is regular(Undecidable)

4.does w belong L(G) is or not (Decidable)

5.does G is Ambigeous(Undecidable)

6.equality of cfg is Undecidable

7.compliment of cfl is undecidable

8.intersection of two cfl is undecidable

9.sigma star is also decidable

Comments

@Munna please chech this question CFG are not closed under sigma star, can you please explane me how sigma star will be decidable for CFG.

https://gateoverflow.in/1553/gate2013_41?show=136872#c136872

Answer 3

There is no algorithm exist by which we can convert CFL to Regular language so Option A undecidable problem.

Emptiness problem is only problem which is decidable under CFL.

Intersetion and complementation are not closed under CFL so it is undecidable problem.

Equality problem L1==L2 is also undecidable problem.

Comments

What about equality of 2 DCFL?

---

Except regular languages all the languages as DCFL,CFL,CSL,Rec and recursive enumerable languages will be UD(undecidable.)

---

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

here it is given that L1 = L2 is decidable for DCFL.