Wed, 23 Jun 2010 21:56:24 +0200

Related articles |
---|

finding a string whether belongs to CFL or not mightydreams@gmail.com (wheatstone) (2010-06-22) |

Re: finding a string whether belongs to CFL or not ott@mirix.org (Matthias-Christian Ott) (2010-06-23) |

Re: finding a string whether belongs to CFL or not gene.ressler@gmail.com (Gene) (2010-06-25) |

Re: finding a string whether belongs to CFL or not ott@mirix.org (Matthias-Christian Ott) (2010-06-25) |

Re: finding a string whether belongs to CFL or not cfc@shell01.TheWorld.com (Chris F Clark) (2010-06-27) |

Re: finding a string whether belongs to CFL or not gene.ressler@gmail.com (Gene) (2010-06-28) |

From: | Matthias-Christian Ott <ott@mirix.org> |

Newsgroups: | comp.compilers |

Date: | Wed, 23 Jun 2010 21:56:24 +0200 |

Organization: | Compilers Central |

References: | 10-06-068 |

Keywords: | parse, theory |

Posted-Date: | 25 Jun 2010 16:25:17 EDT |

On Tue, Jun 22, 2010 at 12:28:05PM -0700, wheatstone wrote:

*> If I am given a string*

*> a^nb^na^n*

*>*

*> where a^n is a to the power n is this language an example of*

*> a) context free,*

*> b)non context free,*

*> c) not context free but whose complement is CF,*

*> d) context free but whose complement is not context free.*

You can prove by the pumping-lemma for context-free languages that

a^nb^na^n is not context-free. The pumping-lemma for context-free

languages is described in a lot of introductory textbooks in

theoretical computer science, some also contain this particular

example.

*> The answer in book is given to be b and c and I am not able to*

a^nb^nc^n is the standard example for a language that is not

context-free.

*> understand what is complement of CF language.*

Given that E is the alphabet of a language L, then its complement

~L is defined as follows: ~L = E* \ L. This means that if you make a

list of all words that you can generate from the alphabet and cross

the words that are in L, you get the complement of L, that is all

words that are not in L.

Regards,

Matthias-Christian

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.