0

As part of the homework we were asked a question about context free languages, and the proof is done using the pumping lemma for CFL. (Prove that it is not a CFL, proof by negation.)

The question is as follows. enter image description here

If I could "ignore" the beginning of the word, we would surely know that language is not CFL (as knowing that it's not a CFL)

But what is the correct treatment at the beginning of the word? Is it really possible to ignore the initial part of the word by arguing that concatenation of a CFL with a CFL leads to a non-CFL?

Thank you

EDIT: Now when I look at the exercise again, I notice that the order of the characters does not matter, so it is not the language I mentioned above.().

Can anyone please give direction or explanation for a possible solution?

StevenU
  • 75
  • 6
  • 1
    If $L$ is context free, so is $c^kL$: just rename the starting symbol $S$ to $S'$ and introduce the new one as $S\to c^kS'$. – Berci Aug 16 '20 at 07:54
  • @Berci Thank you so much for this point, I did not know her. However, it was emphasized in the exercise that the aim is to prove the answers using the pumping lemma only, so grammar/derivation is out of the question here. – StevenU Aug 16 '20 at 08:20
  • 1
    Update, I found a solution to my question, following a similar post on the site several years ago. https://math.stackexchange.com/questions/2269493/pumping-lemma-for-l-w-in-a-b-c-w-text-has-the-same-number-of-a-b-an – StevenU Aug 16 '20 at 11:29

0 Answers0