Example of a non-context free language that nonetheless CAN be pumped?

Problem Detail: 

So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).

Asked By : user2329564

Answered By : Yuval Filmus

The classical example is $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$. Wise shows in his paper A strong pumping lemma for context-free languages that neither the Bar-Hillel pumping lemma nor Parikh's theorem (stating that the set of lengths of words in a context-free language is semi-linear) can be used to prove that $L$ is not context-free. Other tricks like intersecting with a regular language also don't help. (Ogden's lemma, a generalization of the Bar-Hillel pumping lemma, does prove that $L$ is not context-free.) He also provides an alternative pumping lemma which is equivalent to context-freeness (for computable languages), and uses it to prove that $L$ is not context-free.

Wise's pumping lemma states that a language $L$ is context-free if and only if there is an (unrestricted) grammar $G$ generating $L$ and an integer $k$ such that whenever $G$ generates a "sentential form" $s$ (so $s$ can include non-terminals) of length $|s| > k$, we can write $s = uvxyz$ where $x,vy$ are non-empty, $|vxy| \leq k$, and there is a non-terminal $A$ such that $G$ generates $uAz$ and $A$ generates both $vAy$ and $x$.

By repeatedly applying the condition in the lemma, Wise is able to prove that $L$ is not context-free, but the details are somewhat complicated. He also gives an even more complicated equivalent condition, and uses it to prove that the language $\{ a^n b a^{nm} : n,m > 0 \}$ cannot be written as a finite intersection of context-free languages.

If you cannot access Wise's paper (it's behind a paywall), there's a typewritten version which came out as an Indiana university technical report.

---

A non-context-free language which satisfies the pumping condition of Ogden's lemma is given by Johnsonbaugh and Miller, Converse of pumping lemmas, and attributed there to Boasson and Horvath, On languages satisfying Ogden's lemma. The language in question is $$ \begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*} $$ We can write $L' = L_1 \cup L_2$, corresponding to the two different lines. Note that $L_1 \cap L_2 = \emptyset$ and that $L_2$ is regular. Ogden's lemma can be used to prove that $L_1$ is not context-free, and so neither is $L'$, but it cannot be used directly to show that $L'$ is not context-free.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12041