Re: finding a string whether belongs to CFL or not

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

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