|What is the complement of context free language? firstname.lastname@example.org (jianhua li) (2007-06-04)|
|Re: What is the complement of context free language? email@example.com (Roberto Bagnara) (2007-06-09)|
|Re: What is the complement of context free language? firstname.lastname@example.org (Tomasz Kowaltowski) (2007-06-09)|
|Re: What is the complement of context free language? email@example.com (Mustafa Elsheikh) (2007-06-09)|
|From:||Tomasz Kowaltowski <firstname.lastname@example.org>|
|Date:||Sat, 09 Jun 2007 08:52:08 -0300|
|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.
Return to the
Search the comp.compilers archives again.