Fri, 25 Jun 2010 12:55:45 -0700 (PDT)

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: | Gene <gene.ressler@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Fri, 25 Jun 2010 12:55:45 -0700 (PDT) |

Organization: | Compilers Central |

References: | 10-06-068 |

Keywords: | parse, theory |

Posted-Date: | 25 Jun 2010 16:28:24 EDT |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.