Fri, 25 Jun 2010 22:48:56 +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: | Fri, 25 Jun 2010 22:48:56 +0200 |

Organization: | Compilers Central |

References: | 10-06-068 10-06-079 |

Keywords: | parse, theory |

Posted-Date: | 26 Jun 2010 10:53:19 EDT |

On Fri, Jun 25, 2010 at 12:55:45PM -0700, Gene wrote:

*> On Jun 22, 3:28 pm, wheatstone <mightydre...@gmail.com> 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.*

*> >*

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

*> > understand what is complement of CF language.*

*> > Any help would be appreciated.*

*> > Thanks.*

*>*

*> A straightforward application of the pumping lemma for CFL's will show*

*> that your set is not context free. This is why b is a correct answer.*

*>*

*> You'll have to assume the alphabet for this problem is {a,b}.*

*> Consequently, the complement of a^n b^n a^n is the set of all strings*

*> of a's and b's that do _not_ have the form a^n b^n a^n for _any_ n.*

*> So the empty string, aba, and aabbaa are _not_ in the complement. But*

*> a, ab, abaa, .. are in the complement.*

*>*

*> You can with some effort design a CFG that represents this set. Split*

*> up the problem into pieces, considering strings of the form*

*> a^i b^j a^k*

*> where in separate CFG's you force i < j, i > j, j < k, j > k, i < k, i*

*> > k. Then combine all 6 pieces in a union with a single start*

*> symbol.*

*>*

*> Since you can express the complement with a CFG, it's context free,*

*> and c is a correct answer.*

No, context-free grammars are not closed under complement, so your

claim is only true for special cases in which the complement of a

context-sensitive grammar might be context-free.

Regards,

Matthias-Christian

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.