Re: What is the complement of context free language?

Roberto Bagnara <bagnara@cs.unipr.it>
Sat, 09 Jun 2007 00:31:08 -0700

          From comp.compilers
Related articles
What is the complement of context free language? lijh_vc@yahoo.com.cn (jianhua li) (2007-06-04)
Re: What is the complement of context free language? bagnara@cs.unipr.it (Roberto Bagnara) (2007-06-09)
Re: What is the complement of context free language? tk@ic.unicamp.br (Tomasz Kowaltowski) (2007-06-09)
Re: What is the complement of context free language? elsheikhmh@gmail.com (Mustafa Elsheikh) (2007-06-09)
| List of all articles for this month |
From: Roberto Bagnara <bagnara@cs.unipr.it>
Newsgroups: comp.compilers
Date: Sat, 09 Jun 2007 00:31:08 -0700
Organization: Compilers Central
References: 07-06-006
Keywords: parse, theory
Posted-Date: 09 Jun 2007 10:22:07 EDT

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?


The complement of any context-sensitive language is context-sensitive.
Hence the complement of any context-free language is context-
sensitive.
All the best,


          Roberto


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.