Re: finding a string whether belongs to CFL or not

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

Return to the comp.compilers page.
Search the comp.compilers archives again.