0
$\begingroup$

I'm having a hard time with understanding the pumping lemma for CFL. I found this online and can't wrap my head around how it works.

Example 1: Consider L = {0m1m2m | m ≥ 1}.
Pick n of the pumping lemma. Pick z = 0n1n2n.

Break z into uvwxy, with |vwx| ≤ n and vx != ε.
Hence vwx cannot involve both 0s and 2s, since
the last 0 and the first 2 are at least n + 1 positions apart. There are two cases:

• vwx has no 2s. Then vx has only 0s and
1s. Then uwy, which would have to be in
L, has n 2s, but fewer than n 0s or 1s.
• vwx has no 0s. Analogous.
Hence L is not a CFL.

What I don't understand how they can tell the distance between them for example they say:

Hence vwx cannot involve both 0s and 2s, since
the last 0 and the first 2 are at least n + 1 positions apart.

Where do they get the distance n+1 from if I have n= 3, then that will give, 000111222, then the distance will be n and not n+1.

Also how do they know that vmx involves 0s and 2s couldn't all the 0s be in u, for instance, and all 2s be in y.

$\endgroup$

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.