Share
Explore BrainMass

Context-fee language

Thank you for taking the time to look at my problem. I cannot make math symbols, thus, I will let ^ denote "raised to the power." For example, a^2 is a squared or a "raised to the power" of 2. Also, I will use the symbol * to denote multiplication. For example, 2*7=14. Okay, here is my problem:

Show that the language

L={ a^i * b^j * c^k | i>j>k} is not context free.

It is clear that I have to use the pumping lemma for context free-languages (note: do not use pumping lemma for regular languages)

I have choosen my word to be: a^p+1 * b^p * c^p-1. I think that this works , because in the first instance, you can pump down, and loss an a, or you can pump up, to gain a c. I am not sure though what to do if the substring includes a's and c's!

Also, I could use: a^p * b^p-1 *c^p-2. I am having a problem though with all of the cases. In some instances I need to pump down, and in others, I need to pump up.

Please help!

Solution Summary

This solution is comprised of a detailed explanation to show that the language L={ a^i * b^j * c^k | i>j>k} is not context free.

$2.19