home bbs files messages ]

Forums before death by AOL, social media and spammers... "We can't have nice things"

   comp.compilers      Compiler construction, theory, etc. (Mod      2,753 messages   

[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]

   Message 971 of 2,753   
   Mustafa Elsheikh to jianhua li   
   Re: What is the complement of context fr   
   09 Jun 07 08:28:43   
   
   From: elsheikhmh@gmail.com   
      
   On Jun 3, 8:31 pm, jianhua li  wrote:   
   > In many text books, they say that the complememt of context free   
   > language us not context free language .  But they do not say the   
   > complemet of CFL is context sensitive language or Recursively   
   > enumerable language ? So what is the language of the complement of   
   > context free language?   
      
   Complement of CFL could possibly be CFL but not necessarily is.   
   Complement of CFL is both recursive (R) and recursively enumerable   
   (RE). Why? All CFLs are both R and RE. R languages are closed under   
   complement (but RE are not). In that context, complement of CFL is R   
   which is inherently RE.   
      
   -Mustafa   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)   

[   << oldest   |   < older   |   list   |   newer >   |   newest >>   ]


(c) 1994,  bbs@darkrealms.ca