19
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Is this a homework question, or are you just curious? $\endgroup$ May 15, 2013 at 17:00
  • $\begingroup$ This is not a homework but i expect to see it in the exam (just a hunch, knowing my professor). And i am always curious :) $\endgroup$ May 15, 2013 at 17:03
  • 2
    $\begingroup$ We had a similar question, but for regular languages. Same type of construction applies: take a special symbol$\$$ and consider $\$K \cup \{ \$^k \mid k \neq 1\}\{a,b\}^*$ for a nasty language $K\subseteq \{a,b\}^*$. $\endgroup$ May 16, 2013 at 9:42

3 Answers 3

14
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Isn't it needed to be at least one production looking like this: A -> sententialForm1 A sententialForm2 for any pumping to be possible $\endgroup$ May 15, 2013 at 17:32
  • $\begingroup$ Well more general: isn't it needed for a nonterminal B to be part of a sentential form derivable from A such that B->sententialForm1.B.sententialfrom2 is a production of G. Otherwise how would it be certain that a word of an arbitrary length can be pumped from A. $\endgroup$ May 15, 2013 at 17:55
  • $\begingroup$ I don't see why, we do have a production $A \Rightarrow^+ vAy$, which corresponds to pumping. For example, you immediately recover the pumping lemma since $S \Rightarrow^* uAz \Rightarrow^* uv^iAy^iz \Rightarrow^* uv^ixy^iz$. $\endgroup$ May 15, 2013 at 20:59
  • 4
    $\begingroup$ Sounds like a nice addition to our reference. $\endgroup$
    – Raphael
    May 16, 2013 at 5:57
  • $\begingroup$ Another thing missing there is closure under "inverse gsm mappings", see planetmath.org/generalizedsequentialmachine. Perhaps I'll add these at some point. $\endgroup$ May 16, 2013 at 21:38
9
$\begingroup$

Even simpler: $\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$. Can always pump the $a$s; intersection with the regular $\mathcal{L}(a b^+ c^+ d^+)$ gives a non-CFL (and that can be proved by pumping lemma).

$\endgroup$
3
  • 1
    $\begingroup$ This will be a nice addition to the third homework... muahaha $\endgroup$ Dec 22, 2015 at 3:31
  • 1
    $\begingroup$ I don't think this is right. If the language starts with only one $a$, then if you try to pump the $a$ you have to account for the fact that $a^0$ must also be in the language. $\endgroup$
    – MT_
    Oct 15, 2016 at 1:25
  • $\begingroup$ To expand on MCT's comment: consider the word $ab^pc^pd^p$; choose $v=a$, $u=w=x=\varepsilon$, $y=b^pc^pd^p$. Then, for $i=0$, $uv^iwx^iy$ is not in the language, as it doesn't start with an a, so the lemma doesn't hold. $\endgroup$ Dec 10, 2018 at 16:02
3
$\begingroup$

A simple language is $\{a b^n c^n d^n \colon n \ge 1\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$. Intersect with $\mathcal{L}(a b^+ c^+ d^+)$ to get a clearly non-CFL, but you can always pump the $a$, and mimetize the equal-length-ness in the sea of ${}^+$.

$\endgroup$
2
  • $\begingroup$ Wise's example is (apparently) immune to these techniques as well, or so he claims. $\endgroup$ May 15, 2013 at 20:59
  • 4
    $\begingroup$ @YuvalFilmus, so it seems. But my example is immune to professors doubting you understood Wise's paper, or wanting a complete proof that it isn't a CFL in the 2-hour limit of the exam ;-) $\endgroup$
    – vonbrand
    May 15, 2013 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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