Re: finding a string whether belongs to CFL or not

On Tue, Jun 22, 2010 at 12:28:05PM -0700, wheatstone 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.


You can prove by the pumping-lemma for context-free languages that
a^nb^na^n is not context-free. The pumping-lemma for context-free
languages is described in a lot of introductory textbooks in
theoretical computer science, some also contain this particular
example.


> The answer in book is given to be b and c and I am not able to


a^nb^nc^n is the standard example for a language that is not
context-free.


> understand what is complement of CF language.


Given that E is the alphabet of a language L, then its complement
~L is defined as follows: ~L = E* \ L. This means that if you make a
list of all words that you can generate from the alphabet and cross
the words that are in L, you get the complement of L, that is all
words that are not in L.


Regards,
Matthias-Christian

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