0
$\begingroup$

Hi I'm completely stuck on an exercise which is to prove this language is not context free using pumping lemma for context free languages:

L = {xyz | x + y = z} , where the alphabet is from 0-9, so for example
10^m20^m30^m ∈ L for all m ≥ 0 (since 1+2 =3, 10 + 20 = 30, etc)

How would you solve this using the pumping lemma for context free languages? Thank you for your time :)

$\endgroup$
  • $\begingroup$ Try to imitate the proof given here that $a^nb^nc^n$ is not context-free. $\endgroup$ – saulspatz May 18 at 20:56
  • $\begingroup$ I have tried to replicate already and was looking at this video: youtube.com/watch?v=AdfE0IcGaJs&t=57s , but I can't figure out how it connects to amount of 0s etc and I imagine it's not exactly the same. But thank you anyway. @saulspatz $\endgroup$ – Blue shirt May 18 at 21:05
  • $\begingroup$ Simple question. When dividing string = uvxyz, can |u|=0? I'm wondering because if that the case then vxy could contain 10i where i>=p, but I'm not sure. Thank you! @saulspatz $\endgroup$ – Blue shirt May 18 at 21:33
  • $\begingroup$ According to Wikipedia, yes $|u|=0$ is allowed. I can't pretend that I remember all the technicalities of the definition myself. $\endgroup$ – saulspatz May 18 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.