Sat, 09 Jun 2007 08:28:43 -0700

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: | Mustafa Elsheikh <elsheikhmh@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sat, 09 Jun 2007 08:28:43 -0700 |

Organization: | Compilers Central |

References: | 07-06-006 |

Keywords: | parse, theory |

On Jun 3, 8:31 pm, jianhua li <lijh...@yahoo.com.cn> 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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.