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.


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.