# Re: finding a string whether belongs to CFL or not

## Chris F Clark <cfc@shell01.TheWorld.com>Sun, 27 Jun 2010 18:04:32 -0400

From comp.compilers

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)
| List of all articles for this month |

 From: Chris F Clark 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