<p>Yes it is possible. We could use the notion of surface configurations; they were introduced by Cook a long time back.  With this it should be  quite easy to get a version of pumping lemma out. </p>

<p>As to surface configurations, almost any paper on LogCFL should carry its definition. Here is a <a href="http://eccc.hpi-web.de/report/2010/158/revision/1/download/">recent paper</a> and here is a <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.9170&amp;rep=rep1&amp;type=pdf">thesis</a></p>

<p>Maybe someone more energetic can spell out the details!</p>

CC BY-SA 3.0
2011-07-26T18:05:53.683Z
Thanks for answering! Yes, it is pretty natural to look at the combination of automaton state and topmost stack symbol. I am still thinking about this problem, though, and I can't manage to figure out the details... Help is appreciated. :-)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2011-06-13T02:42:35.547Z
2011-06-13T02:42:35.547Z
V Vinay
<p>When discussing this problem with Géraud Sénizergues, he pointed me <a href="https://link.springer.com/article/10.1007%2FBF01752401" rel="nofollow noreferrer">this paper</a> by Sakarovitch that already proves this result. The proof seems to date back to <a href="https://dl.acm.org/citation.cfm?id=805419" rel="nofollow noreferrer">this paper</a> by Ogden. </p>

<p>References:</p>

<ul>
<li>Sakarovitch, Jacques. Sur une propriété d’itération des langages algébriques déterministes. (French. English summary). Math. Systems Theory 14 (1981), no. 3, 247–288.</li>
<li>William F. Ogden. 1969. Intercalation theorems for stack languages. In Proceedings of the first annual ACM symposium on Theory of computing (STOC '69).</li>
</ul>

CC BY-SA 3.0
2018-01-20T13:55:29.987Z
2018-01-20T13:55:29.987Z
Lamine
<p>For completeness a reference to a proof in this direction.</p>

<p>A.Ehrenfeucht, H.J.Hoogeboom, G.Rozenberg: 
Coordinated pair systems. I: Dyck words and classical pumping
RAIRO, Inf. Théor. Appl. 20, 405-424 (1986)</p>

<p>Abstract. 
The notion of a coordinated pair system [...] corresponds very closely to (is another formulation of) the notion of a push-down automaton. In this paper we [...] investigate the possibility of obtaining pumping properties of context-free languages via the analysis of computations in cp systems. In order to do this we analyze the combinatorial structure of Dyck words. The properties of Dyck words we investigate stem from the combinatorial analysis of computations in cp systems. We demonstrate how this correspondence can be used for proving the classical pumping lemma.</p>

CC BY-SA 3.0
2012-12-04T00:26:47.540Z
2012-12-04T00:26:47.540Z
Hendrik Jan
<p>I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! <strong>Update:</strong> I submitted this proof on arXiv, in case this is useful to someone: <a href="http://arxiv.org/abs/1207.2819" rel="noreferrer">http://arxiv.org/abs/1207.2819</a></p>

<p>$\DeclareMathOperator{\fp}{fp}$
$\DeclareMathOperator{\lp}{lp}$
$\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$
$\newcommand{\lpp}[1]{\widehat{\lp{#1}}}$</p>

<p>Let $L$ be a context-free language over an alphabet $\Sigma$. Let $A$ be a
pushdown automaton which recognizes $L$, with stack alphabet $\Gamma$. We denote
by $|A|$ the number of states of $A$. Without loss of generality, we can assume
that transitions of $A$ pop the topmost symbol of the stack and either push no
symbol on the stack or push on the stack the previous topmost symbol and some
other symbol.</p>

<p>We define $p' = |A|^2 |\Gamma|$ and $p = |A| (|\Gamma|+1)^{p'}$ the pumping
length, and will show that all $w \in L$ such that $|w| &gt; p$ have a
decomposition of the form $w = u v x y z$ such that $|vxy| \leq p$, $|vy| \geq
1$ and $\forall n \geq 0, u v^n x y^n z \in L$.</p>

<p>Let $w \in L$ such that $|w| &gt; p$. Let $\pi$ be an accepting path of minimal
length for $w$ (represented as a sequence of transitions of $A$), we denote its
length by $|\pi|$. We can define, for $0 \leq i &lt; |\pi|$, $s_i$ the size of the
stack at position $i$ of the accepting path. For all $N &gt; 0$, we define an
<strong>$N$-level</strong> over $\pi$ as a set of three indices $i, j, k$ with $0 \leq i
&lt; j &lt; k \leq p$ such that:</p>

<ol>
<li>$s_i = s_k, s_j = s_i + N$</li>
<li>for all $n$ such that $i \leq n \leq j$, $s_i \leq s_n \leq s_j$ </li>
<li>for all $n$ such that $j \leq n \leq k$, $s_k \leq s_n \leq s_k$.</li>
</ol>

<p>(For an example of this, see the picture for case 2 below which illustrates an $N$-level.)</p>

<p>We define the level $l$ of $\pi$ as the maximal $N$ such that $\pi$ has an
$N$-level. This definition is motivated by the following property: if the size
of the stack over a path $\pi$ becomes larger than its level $l$, then the stack
symbols more than $l$ levels deep will never be popped. We will now distinguish
two cases: either $l &lt; p'$, in which case we know that the same configuration
for the automaton state and the topmost $l$ symbols of the stack is encountered
twice in the first $p+1$ steps of $\pi$, or $l \geq p'$, and there must be a
stacking and unstacking position that can be repeated an arbitrary number of
times, from which we construct $v$ and $y$.</p>

<p><strong>Case 1.</strong> $l &lt; p'$. We define the configurations of $A$ as the couples
of a state of $A$ and a sequence of $l$ stack symbols (where stacks of size less
than $l$ with be represented by padding them to $l$ with a special blank symbol,
which is why we use $|\Gamma| + 1$ when defining $p$). By definition, there are
$|A| (|\Gamma| + 1)^l$ such configurations, which is less than $p$. Hence, in
the $p+1$ first steps of $\pi$, the same configuration is encountered twice at
two different positions, say $i &lt; j$. Denote by $\widehat{i}$ (resp.
$\widehat{j}$) the position of the last letter of $w$ read at step $i$ (resp.
$j$) of $\pi$. We have $\widehat{i} \leq \widehat{j}$. Hence, we can factor $w =
u v x y z$ with $y z = \epsilon$, $u = w_{0 \cdots \widehat{i}}$, $v =
w_{\widehat{i} \cdots \widehat{j}}$, $x = w_{\widehat{j} \cdots |w|}$. (By $w_{x
\cdots y}$ we denote the letters of $w$ from $x$ inclusive to $y$ exclusive.) By
construction, $|vxy| \leq p$.</p>

<p>We also have to show that $\forall n \geq 0, u v^n x y^n z = u v^n x \in L$, but
this follows from our observation above: stack symbols deeper than $l$ are never
popped, so there is no way to distinguish configurations which are equal
according to our definition, and an accepting path for $u v^n x$ is built from
that of $w$ by repeating the steps between $i$ and $j$, $n$ times.</p>

<p>Finally, we also have $|v| &gt; 0$, because if $v = \epsilon$, then, because we
have the same configuration at steps $i$ and $j$ in $\pi$, $\pi' = \pi_{0 \cdots
i} \pi_{j \cdots |\pi|}$ would be an accepting path for $w$, contradicting the
minimality of $\pi$.</p>

<p>(Note that this case amounts to applying the pumping lemma for regular languages
by hardcoding the topmost $l$ stack symbols in the automaton state, which is
adequate because $l$ is small enough to ensure that $|w|$ is larger than the
number of states of this automaton. The main trick is that we must adjust for
$\epsilon$-transitions.)</p>

<p><strong>Case 2.</strong> $l \geq p'$. Let $i, j, k$ be a $p'$-level. To any stack
size $h$, $s_i \leq h \leq s_j$, we associate the <strong>last push</strong>
$\lp(h) = \max(\{y \leq j | s_y = h\})$ and the <strong>first pop</strong>
$\fp(h) = \min(\{y \geq j | s_y = h\})$.
By definition, $i \leq \lp(h) \leq j$ and $j \leq \fp(h) \leq
k$. Here is an illustration of this construction. To simplify the drawing, I omit the distinction between the path positions and word positions which we will have to do later.</p>

<p><img src="https://i.sstatic.net/AKqjW.png" alt="Illustration of the construction for case 2. To simplify the drawing, the distinction between the path positions and word positions are ommitted."></p>

<p>We say that the <strong>full state</strong> of a stack size $h$ is the triple formed
by:</p>

<ol>
<li>the automaton state at position $\lp(h)$</li>
<li>the topmost stack symbol at position $\lp(h)$</li>
<li>the automaton state at position $\fp(h)$</li>
</ol>

<p>There are $p'$ possible full states, and $p' + 1$ stack sizes between $s_i$ and
$s_j$, so, by the pidgeonhole principle, there exist two stack sizes $g, h$ with
$s_i \leq g &lt; h \leq s_j$ such that the full states at $g$ and $h$ are the same.
Like in Case 1, we define by $\lpp(g)$, $\lpp(h)$, $\fpp(h)$ and $\fpp(g)$ the
positions of the last letters of $w$ read at the corresponding positions in $\pi$.
We factor $w = u v x y z$ where $u = w_{0 \cdots \lpp(g)}$,
$v = w_{\lpp(g) \cdots \lpp(h)}$,
$x = w_{\lpp(h) \cdots \fpp(h)}$,
$y = w_{\fpp(h) \cdots \fpp(g)}$,
and $z = w_{\fpp(g) \cdots |w|}$.</p>

<p>This factorization ensures that $|vxy| \leq p$ (because $k \leq p$ by our
definition of levels).</p>

<p>We also have to show that $\forall n \geq 0, u v^n x y^n z \in L$. To do so,
observe that each time that we repeat $v$, we start from the same state and the
same stack top and we do not pop below our current position in the stack
(otherwise we would have to push again at the current position, violating the
maximality of $\lp(g)$), so we can follow the same path in $A$ and push the
same symbol sequence on the stack. By the maximality of $\lp(h)$ and the
minimality of $\fp(h)$, while reading $x$, we do not pop below our current
position in the stack, so the path followed in the automaton is the same
regardless of the number of times we repeated $v$. Now, if we repeat $w$ as many
times as we repeat $v$, since we start from the same state, since we have pushed
the same symbol sequence on the stack with our repeats of $v$, and since we do
not pop more than what $v$ has stacked by minimality of $\fp(g)$, we can follow
the same path in $A$ and pop the same symbol sequence from the stack. Hence, an
accepting path from $u v^n x y^n z$ can be constructed from the accepting path
for $w$.</p>

<p>Finally, we also have $|vy| &gt; 1$, because like in case 1, if $v =
\epsilon$ and $y = \epsilon$, we can build a shorter accepting path for $w$ by
removing $\pi_{\lp(g)\cdots\lp(h)}$ and $\pi_{\fp(h)\cdots\fp(g)}$.</p>

<p>Hence, we have an adequate factorization in both cases, and the result is
proved.</p>

<p>(Credit goes to Marc Jeanmougin for helping me with this proof.)</p>

CC BY-SA 4.0
2022-04-26T11:57:58.843Z
Do I understand correctly that the size of uvxy is less than p, not just vxy? If so, why isn’t that part of the theorem? It is a stronger statement, after all.
HappyFace
CC BY-SA 4.0
2022-04-26T12:09:56.037Z
After thinking for a while, I see that obviously the length of uvxy might be bigger than p. But the definition of levels say that the whole sequence has been processed from 0 to k<p, so it should mean that uvxy is indeed less than p. So I’m confused.
HappyFace
CC BY-SA 4.0
2022-05-17T16:16:22.600Z
Hi @HappyFace, sorry about the delay in getting back to you. It looks to me as if we could indeed guarantee that $|uvxy| \leq p$, intuitively because the pumping can be made to happen in the beginning of the word. This isn't part of the usual statement of the pumping lemma for CFGs, which I guess is why we didn't claim it, but I don't see why one couldn't additionally ensure this (in both cases of the proof). I'm not sure either why it isn't typically claimed. Why did you convince yourself that after all "the length of uvxy might be bigger than p"?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-04-24T21:11:44.563Z
2012-12-02T14:15:34.933Z
2012-12-02T14:15:34.933Z
Antoine Amarilli 'a3nm'
<p>The <a href="http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages">pumping lemma for regular languages</a> can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, and applying the pigeonhole principle. The <a href="http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages">pumping lemma for context-free languages</a> (as well as Ogden's lemma which is slightly more general), however, is proved by considering a context-free grammar of the language studied, picking a sufficiently long string, and looking at the parse tree.</p>

<p>Given the similarity of the two pumping lemmas, you would expect that the context-free one can also be proved in a similar way to the regular one by considering a pushdown automaton which recognizes the language, rather than a grammar. However, I didn't manage to find any reference to such a proof.</p>

<p>Hence my question: is there a proof of the pumping lemma for context-free languages which only involves pushdown automata and not grammars?</p>

<fl.formal-languages><automata-theory><proofs><grammars>
Proof of the pumping lemma for context-free languages using pushdown automata
Antoine Amarilli 'a3nm'
# Proof of the pumping lemma for context-free languages using pushdown automata

(Asked by: username_0 on 2011-06-10)

The [pumping lemma for regular languages](http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages) can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, and applying the pigeonhole principle. The [pumping lemma for context-free languages](http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages) (as well as Ogden's lemma which is slightly more general), however, is proved by considering a context-free grammar of the language studied, picking a sufficiently long string, and looking at the parse tree.

Given the similarity of the two pumping lemmas, you would expect that the context-free one can also be proved in a similar way to the regular one by considering a pushdown automaton which recognizes the language, rather than a grammar. However, I didn't manage to find any reference to such a proof.

Hence my question: is there a proof of the pumping lemma for context-free languages which only involves pushdown automata and not grammars?

**Tags:** fl.formal-languages, automata-theory, proofs, grammars

---

## 4 answers

### Answer by username_0 on 2012-04-24. Score: 17 | Accepted answer

I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! **Update:** I submitted this proof on arXiv, in case this is useful to someone: <http://arxiv.org/abs/1207.2819>

$\DeclareMathOperator{\fp}{fp}$
$\DeclareMathOperator{\lp}{lp}$
$\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$
$\newcommand{\lpp}[1]{\widehat{\lp{#1}}}$

Let $L$ be a context-free language over an alphabet $\Sigma$. Let $A$ be a
pushdown automaton which recognizes $L$, with stack alphabet $\Gamma$. We denote
by $|A|$ the number of states of $A$. Without loss of generality, we can assume
that transitions of $A$ pop the topmost symbol of the stack and either push no
symbol on the stack or push on the stack the previous topmost symbol and some
other symbol.

We define $p' = |A|^2 |\Gamma|$ and $p = |A| (|\Gamma|+1)^{p'}$ the pumping
length, and will show that all $w \in L$ such that $|w| > p$ have a
decomposition of the form $w = u v x y z$ such that $|vxy| \leq p$, $|vy| \geq
1$ and $\forall n \geq 0, u v^n x y^n z \in L$.

Let $w \in L$ such that $|w| > p$. Let $\pi$ be an accepting path of minimal
length for $w$ (represented as a sequence of transitions of $A$), we denote its
length by $|\pi|$. We can define, for $0 \leq i < |\pi|$, $s\_i$ the size of the
stack at position $i$ of the accepting path. For all $N > 0$, we define an
**$N$-level** over $\pi$ as a set of three indices $i, j, k$ with $0 \leq i
< j < k \leq p$ such that:

1. $s\_i = s\_k, s\_j = s\_i + N$
2. for all $n$ such that $i \leq n \leq j$, $s\_i \leq s\_n \leq s\_j$
3. for all $n$ such that $j \leq n \leq k$, $s\_k \leq s\_n \leq s\_k$.

(For an example of this, see the picture for case 2 below which illustrates an $N$-level.)

We define the level $l$ of $\pi$ as the maximal $N$ such that $\pi$ has an
$N$-level. This definition is motivated by the following property: if the size
of the stack over a path $\pi$ becomes larger than its level $l$, then the stack
symbols more than $l$ levels deep will never be popped. We will now distinguish
two cases: either $l < p'$, in which case we know that the same configuration
for the automaton state and the topmost $l$ symbols of the stack is encountered
twice in the first $p+1$ steps of $\pi$, or $l \geq p'$, and there must be a
stacking and unstacking position that can be repeated an arbitrary number of
times, from which we construct $v$ and $y$.

**Case 1.** $l < p'$. We define the configurations of $A$ as the couples
of a state of $A$ and a sequence of $l$ stack symbols (where stacks of size less
than $l$ with be represented by padding them to $l$ with a special blank symbol,
which is why we use $|\Gamma| + 1$ when defining $p$). By definition, there are
$|A| (|\Gamma| + 1)^l$ such configurations, which is less than $p$. Hence, in
the $p+1$ first steps of $\pi$, the same configuration is encountered twice at
two different positions, say $i < j$. Denote by $\widehat{i}$ (resp.
$\widehat{j}$) the position of the last letter of $w$ read at step $i$ (resp.
$j$) of $\pi$. We have $\widehat{i} \leq \widehat{j}$. Hence, we can factor $w =
u v x y z$ with $y z = \epsilon$, $u = w\_{0 \cdots \widehat{i}}$, $v =
w\_{\widehat{i} \cdots \widehat{j}}$, $x = w\_{\widehat{j} \cdots |w|}$. (By $w\_{x
\cdots y}$ we denote the letters of $w$ from $x$ inclusive to $y$ exclusive.) By
construction, $|vxy| \leq p$.

We also have to show that $\forall n \geq 0, u v^n x y^n z = u v^n x \in L$, but
this follows from our observation above: stack symbols deeper than $l$ are never
popped, so there is no way to distinguish configurations which are equal
according to our definition, and an accepting path for $u v^n x$ is built from
that of $w$ by repeating the steps between $i$ and $j$, $n$ times.

Finally, we also have $|v| > 0$, because if $v = \epsilon$, then, because we
have the same configuration at steps $i$ and $j$ in $\pi$, $\pi' = \pi\_{0 \cdots
i} \pi\_{j \cdots |\pi|}$ would be an accepting path for $w$, contradicting the
minimality of $\pi$.

(Note that this case amounts to applying the pumping lemma for regular languages
by hardcoding the topmost $l$ stack symbols in the automaton state, which is
adequate because $l$ is small enough to ensure that $|w|$ is larger than the
number of states of this automaton. The main trick is that we must adjust for
$\epsilon$-transitions.)

**Case 2.** $l \geq p'$. Let $i, j, k$ be a $p'$-level. To any stack
size $h$, $s\_i \leq h \leq s\_j$, we associate the **last push**
$\lp(h) = \max(\{y \leq j | s\_y = h\})$ and the **first pop**
$\fp(h) = \min(\{y \geq j | s\_y = h\})$.
By definition, $i \leq \lp(h) \leq j$ and $j \leq \fp(h) \leq
k$. Here is an illustration of this construction. To simplify the drawing, I omit the distinction between the path positions and word positions which we will have to do later.

![Illustration of the construction for case 2. To simplify the drawing, the distinction between the path positions and word positions are ommitted.](https://i.sstatic.net/AKqjW.png)

We say that the **full state** of a stack size $h$ is the triple formed
by:

1. the automaton state at position $\lp(h)$
2. the topmost stack symbol at position $\lp(h)$
3. the automaton state at position $\fp(h)$

There are $p'$ possible full states, and $p' + 1$ stack sizes between $s\_i$ and
$s\_j$, so, by the pidgeonhole principle, there exist two stack sizes $g, h$ with
$s\_i \leq g < h \leq s\_j$ such that the full states at $g$ and $h$ are the same.
Like in Case 1, we define by $\lpp(g)$, $\lpp(h)$, $\fpp(h)$ and $\fpp(g)$ the
positions of the last letters of $w$ read at the corresponding positions in $\pi$.
We factor $w = u v x y z$ where $u = w\_{0 \cdots \lpp(g)}$,
$v = w\_{\lpp(g) \cdots \lpp(h)}$,
$x = w\_{\lpp(h) \cdots \fpp(h)}$,
$y = w\_{\fpp(h) \cdots \fpp(g)}$,
and $z = w\_{\fpp(g) \cdots |w|}$.

This factorization ensures that $|vxy| \leq p$ (because $k \leq p$ by our
definition of levels).

We also have to show that $\forall n \geq 0, u v^n x y^n z \in L$. To do so,
observe that each time that we repeat $v$, we start from the same state and the
same stack top and we do not pop below our current position in the stack
(otherwise we would have to push again at the current position, violating the
maximality of $\lp(g)$), so we can follow the same path in $A$ and push the
same symbol sequence on the stack. By the maximality of $\lp(h)$ and the
minimality of $\fp(h)$, while reading $x$, we do not pop below our current
position in the stack, so the path followed in the automaton is the same
regardless of the number of times we repeated $v$. Now, if we repeat $w$ as many
times as we repeat $v$, since we start from the same state, since we have pushed
the same symbol sequence on the stack with our repeats of $v$, and since we do
not pop more than what $v$ has stacked by minimality of $\fp(g)$, we can follow
the same path in $A$ and pop the same symbol sequence from the stack. Hence, an
accepting path from $u v^n x y^n z$ can be constructed from the accepting path
for $w$.

Finally, we also have $|vy| > 1$, because like in case 1, if $v =
\epsilon$ and $y = \epsilon$, we can build a shorter accepting path for $w$ by
removing $\pi\_{\lp(g)\cdots\lp(h)}$ and $\pi\_{\fp(h)\cdots\fp(g)}$.

Hence, we have an adequate factorization in both cases, and the result is
proved.

(Credit goes to Marc Jeanmougin for helping me with this proof.)

> **Comments:**
> **username_4**: Do I understand correctly that the size of uvxy is less than p, not just vxy? If so, why isn’t that part of the theorem? It is a stronger statement, after all.  
> **username_4**: After thinking for a while, I see that obviously the length of uvxy might be bigger than p. But the definition of levels say that the whole sequence has been processed from 0 to k<p, so it should mean that uvxy is indeed less than p. So I’m confused.  
> **username_0**: Hi @HappyFace, sorry about the delay in getting back to you. It looks to me as if we could indeed guarantee that $|uvxy| \leq p$, intuitively because the pumping can be made to happen in the beginning of the word. This isn't part of the usual statement of the pumping lemma for CFGs, which I guess is why we didn't claim it, but I don't see why one couldn't additionally ensure this (in both cases of the proof). I'm not sure either why it isn't typically claimed. Why did you convince yourself that after all "the length of uvxy might be bigger than p"?  

---

### Answer by username_1 on 2011-06-13. Score: 7

Yes it is possible. We could use the notion of surface configurations; they were introduced by Cook a long time back. With this it should be quite easy to get a version of pumping lemma out.

As to surface configurations, almost any paper on LogCFL should carry its definition. Here is a [recent paper](http://eccc.hpi-web.de/report/2010/158/revision/1/download/) and here is a [thesis](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.9170&rep=rep1&type=pdf)

Maybe someone more energetic can spell out the details!

> **Comments:**
> **username_0**: Thanks for answering! Yes, it is pretty natural to look at the combination of automaton state and topmost stack symbol. I am still thinking about this problem, though, and I can't manage to figure out the details... Help is appreciated. :-)  

---

### Answer by username_2 on 2018-01-20. Score: 3

When discussing this problem with Géraud Sénizergues, he pointed me [this paper](https://link.springer.com/article/10.1007%2FBF01752401) by Sakarovitch that already proves this result. The proof seems to date back to [this paper](https://dl.acm.org/citation.cfm?id=805419) by Ogden.

References:

* Sakarovitch, Jacques. Sur une propriété d’itération des langages algébriques déterministes. (French. English summary). Math. Systems Theory 14 (1981), no. 3, 247–288.
* William F. Ogden. 1969. Intercalation theorems for stack languages. In Proceedings of the first annual ACM symposium on Theory of computing (STOC '69).


---

### Answer by username_3 on 2012-12-04. Score: 3

For completeness a reference to a proof in this direction.

A.Ehrenfeucht, H.J.Hoogeboom, G.Rozenberg:
Coordinated pair systems. I: Dyck words and classical pumping
RAIRO, Inf. Théor. Appl. 20, 405-424 (1986)

Abstract.
The notion of a coordinated pair system [...] corresponds very closely to (is another formulation of) the notion of a push-down automaton. In this paper we [...] investigate the possibility of obtaining pumping properties of context-free languages via the analysis of computations in cp systems. In order to do this we analyze the combinatorial structure of Dyck words. The properties of Dyck words we investigate stem from the combinatorial analysis of computations in cp systems. We demonstrate how this correspondence can be used for proving the classical pumping lemma.


---

