Re: finding a string whether belongs to CFL or not

Gene <gene.ressler@gmail.com>
Fri, 25 Jun 2010 12:55:45 -0700 (PDT)

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