Re: finding a string whether belongs to CFL or not

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.

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