Deciadable

Question

I know that whether the complement of a language is of same type? is decidable for RL, DCFL, CSL and RL.But what does it mean clearly.

Is complement of DCFL always DCFL? (or may be regular or CSL)

Is complement of CSL always CSL? (or may be CFL or Regula)

I read many answers here in gateoverflow that say Chomsky hierarchy is used for this?

Please explain?

Answer 1

See as far as the complementation is concerned , following classes of languages follow it :

a) Regular language

b) DCFL

c) CSL

d) Recursive

So if we have original language belonging to any of the above class then its complement language will also belong to the same language..So this problem is a decidable in case a class of language follows a closure property..

But say a language does not follow a closure property of a particular operation under a given class , then the resulant language after applying that concerned operation may or may not belong to that class of language, making the problem as undecidable.. 

And regarding your query on Chomsky hierarchy of language application :

Chomsky hierarchy of language is used when we have operation being performed on languages which belonging to different classes of languages..Or in case closure property fails for a specific class..Let me give me examples belonging to each of these:

Case 1 :

Suppose one language is a CFL and another is recursive..So if we perform union of CFL and recursive , so we push the CFL one to recursive level and we know recursive is closed under union..Hence we can conclude union of CFL and recursive is a recursive language..

Case 2 :

Suppose one language is DCFL and another is CFL..If we do intersection then we have to push DCFL to CFL and we have second language as CFL already..But we know CFL is not closed under intersection , so we push to higher level of Chomsky hierarchy from CFL to CSL for each of the 2 languages..And we know CSL is closed under intersection..

Hence we can conclude that intersection of DCFL and CFL is a CSL for sure...But it may be DCFL or CFL but we cannot guarantee that..

So Chomsky hierarchy along with closure properties gives us the general class of resultant language to which it definitely belongs to..

Comments

Yes exactly..

But u have to keep in mind the properties regular union , regular intersection and regular difference..(L - R) meaning first language is any class and second class is regular..

These properties hold for every class of language..

---

Keep in mind means remember these basic properties for every class.

---

Ya they are not that hard to remember..:)