Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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) |
| From: | Tomasz Kowaltowski <tk@ic.unicamp.br> |
| Newsgroups: | comp.compilers |
| Date: | Sat, 09 Jun 2007 08:52:08 -0300 |
| Organization: | IC/UNICAMP |
| References: | 07-06-006 |
| Keywords: | theory, parse |
| Posted-Date: | 09 Jun 2007 10:23:30 EDT |
> 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 a CFL is obviously not only recursively enumerable but
also recursive. Given a CF grammar G, it is easy to imagine a Turing
machine which checks if a given input string belongs to L(G); if so,
reject reject the input, if not, accept it.
-- tk
Return to the
comp.compilers page.
Search the
comp.compilers archives again.