Sun, 27 Jun 2010 18:04:32 -0400

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: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 27 Jun 2010 18:04:32 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

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

Keywords: | parse, theory |

Posted-Date: | 28 Jun 2010 00:17:22 EDT |

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

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

*>> On Jun 22, 3:28 pm, wheatstone <mightydre...@gmail.com> wrote:*

...

*>> 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.*

Wheatstone wasn't making a general claim, just a specific claim for

that example, and his claim was correct and nicely proven in my book.

You can also extend his claim to work for a larger alphabet. Assume

there are letters c, d, e, ... in the alphabet. The appearance of any

one of them in the string, still is in the complement of a^nb^na^n.

Thus, the result is fully general for *this* non-CFL, it's complement

is a CFL.

Hope this helps,

-Chris

******************************************************************************

Chris Clark email: christopher.f.clark@compiler-resources.com

Compiler Resources, Inc. Web Site: http://world.std.com/~compres

23 Bailey Rd voice: (508) 435-5016

Berlin, MA 01503 USA twitter: @intel_chris

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.