Using Ogden’s Lemma versus regular Pumping Lemma for Context-Free Grammars

Question

I'm learning the difference between the lemmata in the question. Every reference I can find uses the example:

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}

to show the difference between the two. I can find an example using the regular lemma to "disprove" it.

Select w = uvxyz, s.t. |vy| > 0, |vxy| <= p. Suppose w contains an equal number of b's, c's, d's.

I selected:

u,v,x = ε
y = (the string of a's)
z = (the rest of the string w)

Pumping y will just add to the number of a's, and if |b|=|c|=|d| at first, it still will now.

(Similar argument for if w has no a's. Then just pump whatever you want.)

My question is, how does Ogden's lemma change this strategy? What does "marking" do?

Thanks!

Hagridden

Answer 1

One important stumbling issue here is that "being able to pump" does not imply context free, rather "not being able to pump" shows it is not context free. Similarly, being grey does not imply you're an elephant, but being an elephant does imply you're grey...

Grammar context free        => Pumping Lemma is definitely satisfied  
Grammar not context free    => Pumping Lemma *may* be satisfied
Pumping Lemma satisfied     => Grammar *may* be context free
Pumping Lemma not satisfied => Grammar definitely not context free
# (we can write exactly the same for Ogden's Lemma)
# Here "=>" should be read as implies

That is to say, in order to demonstrate that a language is not context free we must show it fails(!) to satisfy one of these lemmata. (Even if it satisfies both we haven't proved it is context free.)

Below is a sketch proof that L = { a^i b^j c^k d^l where i = 0 or j = k = l} is not context free (although it satisfies The Pumping Lemma, it doesn't satisfy Ogden's Lemma):

Pumping lemma for context free grammars:

If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a pumping length) can be written as s = uvxyz
with substrings u, v, x, y and z, such that:
1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. u v^n x y^n z is in L for every natural number n.

In our example:

For any s in L (with |s|>=p):

• If s contains as then choose v=a, x=epsilon, y=epsilon (and we have no contradiction to the language being context-free).
• If s contains no as (w=b^j c^k d^l and one of j, k or l is non-zero, since |s|>=1) then choose v=b (if j>0, v=c elif k>0, else v=c), x=epsilon, y=epsilon (and we have no contradiction to the language being context-free).

(So unfortunately: using the Pumping Lemma we are unable to prove anything about L!
Note: the above was essentially the argument you gave in the question.)

Ogden's Lemma:

If a language L is context-free, then there exists some number p > 0 (where p may or may not be a pumping length) such that for any string w of length at least p in L and every way of "marking" p or more of the positions in w, w can be written as w = uxyzv
with strings u, x, y, z, and v such that:
1. xz has at least one marked position,
2. xyz has at most p marked positions, and
3. u x^n y z^n v is in L for every n ≥ 0.

Note: this marking is the key part of Ogden's Lemma, it says: "not only can every element be "pumped", but it can be pumped using any p marked positions".

In our example:

Let w = a b^p c^p d^p and mark the positions of the bs (of which there are p, so w satisfies the requirements of Ogden's Lemma), and let u,x,y,z,v be a decomposition satisfying the conditions from Ogden's lemma (z=uxyzv).

• If x or z contain multiple symbols, then u x^2 y z^2 w is not in L, because there will be symbols in the wrong order (consider (bc)^2 = bcbc).
• Either x or z must contain a b (by Lemma condition 1.)

This leaves us with five cases to check (for i,j>0):

• x=epsilon, z=b^i
• x=a, z=b^i
• x=b^i, z=c^j
• x=b^i, z=d^j
• x=b^i, z=epsilon

in every case (by comparing the number of bs, cs and ds) we can see that u x^2 v y^2 z is not in L (and we have a contradiction (!) to the language being context-free, that is, we've proved that L is not context free).

.

To summarise, L is not context-free, but this cannot be demonstrated using The Pumping Lemma (but can by Ogden's Lemma) and thus we can say that:

Ogden's lemma is a second, stronger pumping lemma for context-free languages.

Marbles

What is this "marking" in Ogden's lemma all sources keep talking about, but none cares to explain? – Ether

@Ether Great question! In many papers you see Ogden's Lemma refer to "marked symbols" i.e. a subset of the alphabet, considering the symbols in this subset "marked". In the example above the alphabet is {a, b, c, d} and the "marked symbols" are {b}. Now, either "marked positions" means the same as marked symbols OR it may be a slight generalization / weaker, I haven't found a precise definition yet... – Marbles

@Ether the set of marked positions in a word $w$ of length $n$ is nothing else than a subset of its positions $\{1,\ldots,n\}$. A symbol can of course occur multiple times in a word, and the notion of "position" refers to a single such occurrence. In the word $a b^p c^p d^p$, if we mark all $b$s then the marked positions consist of $\{2,3,4,\ldots, p, p+1\}$. A precise and illustrated explanation on Ogden's Lemma is found in Harrison, Introduction to Formal Language Theory, Addison-Wesley 1978, Chapter 6.2 – Sessler

Answer 2

I'm not too sure about how to use Ogden's lemma here but your "proof" is wrong. When using the pumping lemma to prove that a language is not context free you cannot choose the splitting into uvxyz. The splitting is chosen "for you" and you have to show that the lemma is not fulfilled for any uvxyz.

Ralston

No, you can choose it, that's why Ogden's Lemma is more useful than the regular pumping lemma. The regular one corresponds to the choice of marking all the positions. – Crenulation

@Ralston the point is, you can choose the set of marked positions, but then the splitting uvxyz is chosen for you. Observe that the proof chooses (only) the marked positions, but the argument indeed continues with a splitting that is "chosen for you", so the proof is correct. – Sessler