Complementation of a language

Question

HI

I am new in preparing gate , I got confused in complementation operation , as per my understanding, if a language is L it's complement L' it won't be having any string present in L which triggers me a doubt suppose a language is L which is regular , which complementation will be having any thing except L suppose it can be recursive or context sensitive but we know complement of regular is closed operation. So which is contradicting me as I am thinking then context sensitive language also having FA as it is under L' (complement). Please clarify it . I think my understanding on complementation is wrong. TIA

Answer 1

• If L is a regular language . Then its complement L' must be regular . Becz regular language is closed under complement.

• Example :

L=a.       -----------> regular

L'=aaa*+  null   ----------> regular

• If L is regular then it is cfl,csl or recursive also . Becz regular language is subset of all these.

• Regular$\sqsubseteq$cfl$\sqsubseteq$csl$\sqsubseteq$rec$\sqsubseteq$r.e

Comments

@abhishekmehta4u Sir I think L' will be $\left ( \epsilon +aa^+ \right )$

Answer 2

a doubt suppose a language is L which is regular, which complementation will be having any thing except L suppose it can be recursive or context sensitive  

but we know complement of regular is closed operation...

yes you are absolutely true L' can be recursive or context sensitive or CFL but it isn't mean that L' is not RL

Note that every RL is CFL and Every CFL is CSL and Every CSL is recursive and Every Recursive is Recursive Enumarable but converse is not true

If you didn't understand till now... L is a regular language ===> there exist atleast one DFA ==> interchange the final and non-final states it accepts L'