UGC self doubt

Question

According to closure properties chart DCFL are closed under the complimentations but CFL's are not.

L= 0ⁿ1ⁿ | n≥0 is DCFL so L' will also be DCFL.  Again L^k is for any k≥1 means L to power any k≥1 should not be DCFL because DCFL's are not closed under union. where I am wrong Sir? 

Comments

@Divyanshum29  Sir , not closed means may or may not be... DCFLs are not closed under union/kleene star/kleene plus operations. It means after these operations , resulting language may  or may not be DCFL. So, on the basis of closure property we can't say the class of resulting language here. But since CFLs are closed under union/kleene star/kleene plus operations . So, We can say that resulting language will be CFL based on the closure properties.

Here , L is DCFL. So , it should also be CFL because CFLs are proper superset of DCFLs. So, we can say that L^k for any k >= 1 will be CFL because CFLs are closed under kleene star/kleene plus operation.

please check :- https://gatecse.in/closure-property-of-language-families/  

 

---

Thanks for this clarification, but I have 1 more doubt, how to overcome these problems when language looks like DCFL but we can not use the dcfl properties, Is it always right that if a language is DCFL we will consider it as CFL and use the CFL'S closure properties.

---

yes. go to next level of language class , if it is closed under that class then resulting language will come within that class but if it not closed then again go to next level  and do the same procedure.

for example , if L₁ and L₂ are DCFL. then L₁ $\cap$ L₂ may or may not be DCFL because DCFLs are not closed under intersection operation. So, upgrade L₁ and L₂ . So, now L₁ and L₂ are CFL. now again L₁  $\cap$ L₂  may or may not be CFL because CFLs are also not closed under intersection operation. So, again upgrade L₁ and L₂. So, now L₁ and L₂ are CSL. Now,  L₁ $\cap$ L₂ is definitely CSL because CSLs are closed under intersection operation. So, here L₁ $\cap$ L₂ is definitely CSL but it does not mean that it is not DCFL and CFL . It may or may not be..

---

Got it.:) Thanks @ankit

---

@Ankit can you give an example for "DCFLs not closed under Kleen closure." ? I can find examples for union & concatenation but not Kleen star.