15
$\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$
  • $\begingroup$ Is this a homework question, or are you just curious? $\endgroup$ – Yuval Filmus May 15 '13 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$ – user2329564 May 15 '13 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$ – Hendrik Jan May 16 '13 at 9:42
13
$\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$
  • $\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$ – user2329564 May 15 '13 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$ – user2329564 May 15 '13 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$ – Yuval Filmus May 15 '13 at 20:59
  • 4
    $\begingroup$ Sounds like a nice addition to our reference. $\endgroup$ – Raphael May 16 '13 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$ – Yuval Filmus May 16 '13 at 21:38
8
$\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$
  • 1
    $\begingroup$ This will be a nice addition to the third homework... muahaha $\endgroup$ – Renato Sanhueza Dec 22 '15 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$ – MCT Oct 15 '16 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$ – potestasity Dec 10 '18 at 16:02
2
$\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$
  • $\begingroup$ Wise's example is (apparently) immune to these techniques as well, or so he claims. $\endgroup$ – Yuval Filmus May 15 '13 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 '13 at 21:04

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.