Consider the language $L = \{w \in \Sigma^* \mid $ the maximum number of a's following a b is equal to the maximum number of b's following an a$\}$ over the alphabet $\Sigma = \{a,b\}$. So for example abbaab is in L, as there are at most 2 consecutive b's after an a and at most 2 consecutive a's after a b. Yet abbaba is not.
We can show using the pumping lemma for regular languages that L is not regular. Yet my colleague and I have failed to use the pumping lemma for context-free languages to show that L is not context-free, yet at the same time creating a PDA/CFG for this also seems impossible as it would need to remember the maximum it has encountered somewhere somehow. Just the stack of a PDA does not seem sufficient for this purpose.
So is $L$ context free?
To use the pumping lemma for context-free languages to show that L is not context-free, we need to do the following:
We assume that L is context-free, p is the pumping length of L. Choose a string w in L that has length at least p. $w = ab^p a^p b$ suffices. Then showing that dividing w in every possible way into five parts u, v, x, y and z such that $|vxy| ≤ p$ and $|vy| ≥ 1$, the string $uv^k xy^k z$ is not in L for some $k ≥ 0$.
We divide w as follows:
$u = ab^{p-1}$
$v = b$
$x = a^{p-1}$
$y = \epsilon$
$z = ab$
The properties are still valid:
Then $uv^2 xy^2 z = ab^{p+1} a^{p} b$, which is not in L because the maximum number of a’s following a b is $p$, but the maximum number of b’s following an a is $p+1$. We observe that this division contradicts the pumping property, and L is not context free.