Pumping Theorem and K

Question

I have an example from a textbook using a language $L = \{ a^nb^ma^n : m, n \ge 0, n \ge m \}$.

We can use pumping theorem to show that $L$ is not context-free. If it were, then there would exist some $k$ such that any string $w$, where $|w| \ge k$, must satisfy the conditions of the theorem. We show one string $w$ that does not. Let $w =a^kb^ka^k$ where $k$ is the constant from the pumping theorem [...]

• Why have they chosen to use $k$? My understanding from the pumping theorem definition is that $k$ is an arbitrary integer $>1$
• What is the relation of $k$ to $n$ and $m$ in the original language definition?
• Members of $L$ can have more $a$'s than $b$'s, but $a^kb^ka^k$ will result in an equal number of $a, b$. Is it not necessary in this case because an equal number of $a$'s and $b$'s is still a member of L? What happens when $L = \{ a^nb^ma^n : m, n \ge 0, n > m \}$ and $a^kb^ka^k$ is not part of $L$?

I think this is holding me back from understanding how to prove my homework question of:

Prove whether the language $\{a^xb^yc^xd^y: x, y \ge 0\}$ is context free or not

Apologies if these are basic. I've been racking my brain for days on these kinds of questions and I'm so lost. Thanks for any assistance.

Answer 1

Definition from Wikipedia:

If a language L is context-free, then there exists some integer p ≥ 1 (called a "pumping length"[1]) such that every string s in L that has a length of p or more symbols (i.e. with |s| ≥ p) can be written as

s = uvwxy

with substrings u, v, w, x and y, such that

1. |vwx| ≤ p,
2. |vx| ≥ 1, and
3. $uv^nwx^ny$ is in L for all n ≥ 0.

k is called the pumping length and it's a positive integer. (it can be equal to 1).

k is NOT an arbitrary integer and every CFL is guaranteed to have one.

They chose the string w, since it's a contradicting example. (it's not a unique contradicting example)

I advise you to separate the string w (s in the definition) to different cases for-each position of v and x might be (which satisfy (!) the properties in the definition) and see if choosing some n (0 ... inf) creates a word that is not in L.

If w is in L and don't satisfy the pumping lemma (all the possible cases resolved in contradictions) -> L is not a CFL.

[Note that n=0 will remove x and v from the string, which sometimes help]

[Notice that w (in your example) is $\geq$ k, that's why you can use the pumping lemma. For strings that are shorter, you can't use it.]

For example (1 case): if v and x consists only of 'b', choosing n = 2 will create a string with number of 'b' strictly larger than 'a' which is not satisfying L properties.

k has no relation to n and m, it's a constant. For each CFL you are guaranteed to have one.

Hint for your homework : a possible contradicting example choice is very similar to your example.