What is the complement of context free language?

[jianhua li]

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?

[Roberto Bagnara]

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

[Tomasz Kowaltowski]

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

[Mustafa Elsheikh]

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

[jianhua li]

Mr Roberto wrote:

>The complement of any context-sensitive language is
>context-sensitive.
>Hence the complement of any context-free language is
>context-sensitive.

We acknowledge the complement of CFL is CSL. But this language is
the subset of CSL or the full set of CSL ? I think the complement of
CFL is the subset of CSL. Otherwise, that means CSL can be expressed
by the complement of CFL. Is there any theoretical proving?

lijh

___________________________________________________________
G@W"QE;"Cb7QSJOd3.5GH]A?#,20M8=<~#!
http://cn.mail.yahoo.com