<p><strong>Counter Automata</strong></p>

<p>I was a co-author for a paper where we investigated this problem for counter automata.  We were able to show that the length of a shortest string accepted by an <span class="math-container">$n$</span>-state (non-empty) counter automaton is at most <span class="math-container">$\Theta(n^2)$</span>.  See here: <a href="https://lmcs.episciences.org/5251" rel="nofollow noreferrer">https://lmcs.episciences.org/5251</a></p>

<p>The lower bound can be obtained similar to how you described in your question with cycles of length <span class="math-container">$p$</span> and <span class="math-container">$q$</span> (or any two relatively prime numbers).</p>

<hr>

<p><strong>Pushdown Automata</strong></p>

<p><em>Upper Bound:</em> We can get an upper bound using standard techniques.  The length of a shortest string accepted by an <span class="math-container">$n$</span>-state (non-empty) pushdown automaton is at most <span class="math-container">$2^{O(n^2)}$</span>.</p>

<p>Essentially, we argue that if the pushdown automaton's language is non-empty, then there exists some string that it accepts where the stack height is at most <span class="math-container">$O(n^2)$</span>.  Therefore, there are at most <span class="math-container">$n \cdot 2^{O(n^2)}$</span> (which is still <span class="math-container">$2^{O(n^2)}$</span>) possible configurations so there must be an accepted string of length at most <span class="math-container">$2^{O(n^2)}$</span>.</p>

<p><em>Lower Bound:</em> For an exponential lower bound, see Jeffrey's answer above.</p>

<p>Also, see my answer to this related question: <a href="https://cstheory.stackexchange.com/questions/37492/shortest-string-in-the-intersection-of-a-context-free-language-and-a-regular-lan/37502#37502">Shortest string in the intersection of a context-free language and a regular language</a></p>

<p>This related answer leads to a deterministic binary stack (non-empty) PDA with an exponential lower bound for the length of a shortest accepted string.  Note that the construction relies on the fact that logspace bounded auxiliary pushdown automata can run for exponential time.</p>

<p>For example, such a machine could iterate through the numbers from <span class="math-container">$0$</span> to <span class="math-container">$2^n - 1$</span> in binary on the stack using only <span class="math-container">$O(\log(n))$</span> auxiliary space.</p>

<hr>

<p><strong>Update: A Tight Bound</strong></p>

<p>Due to results from [1] (Theorems 3.19 and 4.22), it follows that there is a tight bound.  That is, the length of a shortest string accepted by an <span class="math-container">$n$</span>-state (non-empty) pushdown automaton is at most <span class="math-container">$2^{\Theta\left(\frac{n^2}{\log(n)}\right)}$</span>.  This assumes a restriction on the PDA's such that the stack alphabet is fixed and the stack pushes or pops only one symbol at a time.</p>

<p>After looking through the proofs of Theorems 3.19 and 4.22, as far as I can tell, this result should hold for both deterministic and non-deterministic PDA's.</p>

<p><em>Note:</em> I find their proofs difficult to fully verify / reconstruct.  Does anyone know of a simplified argument?  If not, I would always be interested in looking through this further with others.</p>

<hr>

<p><strong>How To Apply Results From [1]</strong></p>

<p><em>Rational Index:</em> The rational index of a language <span class="math-container">$L$</span> is a function <span class="math-container">$r$</span> such that for every <span class="math-container">$n$</span>, <span class="math-container">$r(n)$</span> is the maximum length of a shortest string in <span class="math-container">$L \cap L(A)$</span> over all <span class="math-container">$n$</span>-state non-deterministic finite automata <span class="math-container">$A$</span>.  In other words, <span class="math-container">$r(n) := max_{A}\{ \; min_{x}\{ \; \vert x \vert \; : \; x \in L \cap L(A) \; \} \; \}$</span> where <span class="math-container">$A$</span> is an <span class="math-container">$n$</span>-state NFA and <span class="math-container">$x$</span> is a finite string.  A definition for rational index can also be found in [2].</p>

<p><em>Lower Bound:</em> By Theorem 3.19 from [1], we get an <span class="math-container">$2^{\Omega\left(\frac{n^2}{\log(n)}\right)}$</span> lower bound.  This is because there is some fixed context-free language <span class="math-container">$L$</span> whose rational index is <span class="math-container">$2^{\Omega\left(\frac{n^2}{\log(n)}\right)}$</span>.</p>

<p>Let me explain.  Let <span class="math-container">$P$</span> denote a PDA that recognizes <span class="math-container">$L$</span>.  By the preceding, there is an infinite family <span class="math-container">$\{ A_n \}_{n \in \mathbb{N}}$</span> of finite automata such that for all <span class="math-container">$n$</span>, <span class="math-container">$A_n$</span> has <span class="math-container">$n$</span> states and asymptotically a shortest string accepted by the Cartesian product of <span class="math-container">$A_n$</span> with <span class="math-container">$P$</span> has length <span class="math-container">$2^{\Omega\left(\frac{n^2}{\log(n)}\right)}$</span>.</p>

<p>It looks to me that, each finite automaton <span class="math-container">$A_n$</span> from their construction is deterministic.  Also, the PDA <span class="math-container">$P$</span> is deterministic with a fixed stack alphabet that only pushes or pops one symbol at a time.  Therefore, the lower bound applies to deterministic PDA's with a fixed stack alphabet that only push or pop one symbol at a time. </p>

<p><em>Upper Bound:</em> By Theorem 4.22 from [1], we get an <span class="math-container">$2^{O\left(\frac{n^2}{\log(n)}\right)}$</span> upper bound.  This is because any given context-free language has rational index <span class="math-container">$2^{O\left(\frac{n^2}{\log(n)}\right)}$</span>.</p>

<p>Let me explain.  Given any <span class="math-container">$n$</span>-state PDA <span class="math-container">$P$</span> over a fixed alphabet that only pushes or pops one symbol at a time, we can convert it into an associated <span class="math-container">$O(n)$</span>-state visibly pushdown automaton <span class="math-container">$P^{\prime}$</span> over a larger alphabet that must read a push-<span class="math-container">$c$</span> symbol in order to push <span class="math-container">$c$</span> onto the stack and a pop-<span class="math-container">$c$</span> symbol in order to pop <span class="math-container">$c$</span> off of the stack for each stack symbol <span class="math-container">$c$</span>.  The PDA's <span class="math-container">$P$</span> and <span class="math-container">$P^{\prime}$</span> have shortest accepted strings of similar length.</p>

<p>We can now view <span class="math-container">$P^{\prime}$</span> as the Cartesian product of a fixed PDA and an <span class="math-container">$O(n)$</span>-state finite automaton.  The fixed PDA's language has rational index <span class="math-container">$2^{O\left(\frac{n^2}{\log(n)}\right)}$</span> meaning that a shortest string accepted by <span class="math-container">$P^{\prime}$</span> has length at most <span class="math-container">$2^{O\left(\frac{n^2}{\log(n)}\right)}$</span>.  Therefore, a shortest string accepted by <span class="math-container">$P$</span> has length at most <span class="math-container">$2^{O\left(\frac{n^2}{\log(n)}\right)}$</span>.</p>

<hr>

<p><strong>References</strong></p>

<p>[1] <em>Pierre, Laurent</em>, <a href="http://dx.doi.org/10.1016/0304-3975(92)90269-L" rel="nofollow noreferrer"><strong>Rational indexes of generators of the cone of context-free languages</strong></a>, Theor. Comput. Sci. 95, No. 2, 279-305 (1992). <a href="https://zbmath.org/?q=an:0745.68068" rel="nofollow noreferrer">ZBL0745.68068</a>.</p>

<p>[2] <em>Deleage, Jean-Luc; Pierre, Laurent</em>, <a href="http://dx.doi.org/10.1016/0304-3975(86)90158-1" rel="nofollow noreferrer"><strong>The rational index of the Dyck language (D_ 1^{’*})</strong></a>, Theor. Comput. Sci. 47, 335-343 (1986). <a href="https://zbmath.org/?q=an:0632.68072" rel="nofollow noreferrer">ZBL0632.68072</a>.</p>

CC BY-SA 4.0
2020-04-08T17:29:22.317Z
2020-04-12T19:26:40.047Z
2020-04-12T19:26:40.047Z
Michael Wehar
<p>The <em>precise</em> answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &amp;Ullman).  And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols.  For example, a classic construction turns a grammar like</p>

<p><span class="math-container">$S \rightarrow X_1 X_1$</span></p>

<p><span class="math-container">$X_1  \rightarrow X_2 X_2$</span></p>

<p><span class="math-container">$X_2 \rightarrow X_3 X_3$</span> </p>

<p>...</p>

<p><span class="math-container">$X_{n-1} \rightarrow X_n X_n$</span></p>

<p><span class="math-container">$X_n \rightarrow a$</span></p>

<p>into a 3-state machine accepting the language <span class="math-container">$\{\,a^{2^n}\,\}$</span> by final state, no matter how many variables there are, or into a 1-state machine accepting by empty stack.  This gives a classic example of how the shortest string can be exponential in the description size of the PDA.</p>

CC BY-SA 4.0
2019-11-29T00:52:13.420Z
Could you please explain this "classic construction"? I can't find anything about it online.
Antimony
CC BY-SA 4.0
2019-12-16T18:52:36.240Z
Naturally, most of the classic proofs are not online (at least not the original version). I found that the proof of Theorem 5.4.1 in M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978 (the "pumping lemmings book") contains the construction of a 1-state pda accepting with empty stack. Its stack alphabet is identical to the variables of the grammar. I warmly recommend working through this book - it discusses several descriptional complexity questions like the one you asked.
Hermann Gruber
CC BY-SA 4.0
2019-12-16T18:59:43.980Z
Ah yes- and Jeffrey's answer refers to nondeterministic  PDAs, which was not exactly what you were asking for.
Hermann Gruber
CC BY-SA 4.0
2019-11-24T21:40:17.440Z
2020-04-08T17:33:54.127Z
2020-04-08T17:33:54.127Z
Jeffrey Shallit
<p>(Answer inspired by Lamine's comment)</p>

<p>We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack alphabet of size <span class="math-container">$k$</span>, we can construct an automaton that accepts a word of length <span class="math-container">$O(n^{k+c})$</span>. </p>

<p>The basic idea is to just make the stack as large as possible, and then accept a unary word of that length. If we have stack symbols <span class="math-container">$a_1, a_2, \dots, a_k$</span>, we can construct the automaton as follows:</p>

<p>If the top symbol is <span class="math-container">$a_k$</span>, pop it and transition to a sequence of <span class="math-container">$n/k$</span> states that each accept a character of input. Otherwise, if the top of the stack is <span class="math-container">$a_i$</span>, pop it and transition to a sequence of <span class="math-container">$n/k$</span> states which pushes <span class="math-container">$n/k$</span> copies of <span class="math-container">$a_{i+1}$</span> onto the stack. This results in accepting a single word of length <span class="math-container">$O((n/k)^k)$</span>.</p>

<p>Edit: It turns out that you can simulate <span class="math-container">$k$</span> stack symbols using only <span class="math-container">$2$</span> stack symbols, by using a <span class="math-container">$\log(k)$</span> depth tree of states to "pop" symbols from the stack and a sequence of <span class="math-container">$\log(k)$</span> sequence of states to "push" symbols onto the stack. This means that with only two stack symbols, you can still have a minimum word that is nearly exponential in <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2019-11-24T13:29:44.480Z
I don't understand why the stack alphabet should be in $\Omega(N)$. The conversion between a CFG and a PDA preserves the input alphabet size, which is the same as the stack alphabet. See the conversion algorithm in "Introduction to automata theory, languages and computation" by Hopcroft et al.
Lamine
CC BY-SA 4.0
2019-11-24T13:37:03.040Z
Moreover, you can convert your solution giving a word of length $\Omega(n/k)^k$ into a solution giving a word of length $\Omega(\sqrt{n}3^{\Omega(\sqrt{n})})$ by "emulating" each terminal $a_i$ $(1\leq i\leq k)$ by a subword $ab^i a$ and slightly transforming the PDA. You get a solution with superpolynomial length and only two protocols.
Lamine
CC BY-SA 4.0
2019-11-24T13:39:05.273Z
However, one has to check if the new construction is still deterministic.
Lamine
CC BY-SA 4.0
2019-12-20T20:24:01.610Z
@Lamine I just realized that you don't even need the unary encoding you proposed. You can just use a binary encoding to simulate a stack alphabet of size $k$ using $log(k)$ symbols from a 2-symbol alphabet with a corresponding $log(k)$ blowup in state size when writing to the stack and $k$ blowup when reading from the stack. This results in a nearly exponential solution.
Antimony
CC BY-SA 4.0
2019-11-23T16:07:08.043Z
2019-12-29T11:53:23.883Z
2019-12-29T11:53:23.883Z
Antimony
<p>Given a fixed alphabet, consider all deterministic pushdown automata with <span class="math-container">$n$</span> states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic pushdown automaton with <span class="math-container">$n$</span> states (holding alphabet size constant)? </p>

<p>I found an example where the shortest word is <span class="math-container">$\Omega(n^2)$</span> and suspect that this bound is tight, but have been unable to prove it. Everything I found online talking about shortest words is talking about finite or two-way automata only, not pushdown automata.</p>

<p>As an example, choose two large prime numbers <span class="math-container">$p$</span> and <span class="math-container">$q$</span>, and two input symbols <span class="math-container">$a$</span> and <span class="math-container">$b$</span>. Create an automaton with a cycle of length <span class="math-container">$p$</span> that reads an <span class="math-container">$a$</span> and pushes onto the stack, with a transition to a cycle of length <span class="math-container">$q$</span> that reads a <span class="math-container">$b$</span> and pops from the stack. </p>

<p>By placing the initial and accept states at appropriate places on the first and second cycle, you force the automaton to go through the first cycle <span class="math-container">$q-1$</span> times and the second cycle <span class="math-container">$p-1$</span> times, so that the maximum stack length is the same modulo <span class="math-container">$p$</span> and <span class="math-container">$q$</span>, and thus the shortest word has length <span class="math-container">$\Omega(pq)$</span>. Since the automaton has <span class="math-container">$p+q$</span> states, this means the shortest word is <span class="math-container">$\Omega(n^2)$</span>.</p>

CC BY-SA 4.0
2019-11-23T15:32:11.717Z
For "general" (not necessarily deterministic) PDAs, you can build examples where the shortest word is in $2^{\Omega(n)}$. For a given CFG of size $n$, there is always a PDA of size at most $O(n^3)$ accepting the language generated by the CFG. And we know that the length of shortest word generated by a CFG can be exponential in its size. So you get a trivial example in $\Omega(2^{\Omega(\sqrt[3]{n})})$.
Lamine
CC BY-SA 4.0
2019-11-23T15:56:45.363Z
Thanks. I think the construction works for deterministic PDAs too, so the answer is exponential. It does however require a stack alphabet of size O(n), as far as I can tell. I think with a fixed stack alphabet, it becomes polynomial again.
Antimony
<fl.formal-languages><automata-theory><lower-bounds><context-free>
Maximum shortest word accepted by pushdown automata
Antimony
# Maximum shortest word accepted by pushdown automata

(Asked by: username_0 on 2019-11-23)

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic pushdown automaton with $n$ states (holding alphabet size constant)?

I found an example where the shortest word is $\Omega(n^2)$ and suspect that this bound is tight, but have been unable to prove it. Everything I found online talking about shortest words is talking about finite or two-way automata only, not pushdown automata.

As an example, choose two large prime numbers $p$ and $q$, and two input symbols $a$ and $b$. Create an automaton with a cycle of length $p$ that reads an $a$ and pushes onto the stack, with a transition to a cycle of length $q$ that reads a $b$ and pops from the stack.

By placing the initial and accept states at appropriate places on the first and second cycle, you force the automaton to go through the first cycle $q-1$ times and the second cycle $p-1$ times, so that the maximum stack length is the same modulo $p$ and $q$, and thus the shortest word has length $\Omega(pq)$. Since the automaton has $p+q$ states, this means the shortest word is $\Omega(n^2)$.

**Tags:** fl.formal-languages, automata-theory, lower-bounds, context-free
> **Comments:**
> **username_1**: For "general" (not necessarily deterministic) PDAs, you can build examples where the shortest word is in $2^{\Omega(n)}$. For a given CFG of size $n$, there is always a PDA of size at most $O(n^3)$ accepting the language generated by the CFG. And we know that the length of shortest word generated by a CFG can be exponential in its size. So you get a trivial example in $\Omega(2^{\Omega(\sqrt[3]{n})})$.  
> **username_0**: Thanks. I think the construction works for deterministic PDAs too, so the answer is exponential. It does however require a stack alphabet of size O(n), as far as I can tell. I think with a fixed stack alphabet, it becomes polynomial again.  

---

## 3 answers

### Answer by username_2 on 2020-04-08. Score: 5 | Accepted answer

**Counter Automata**

I was a co-author for a paper where we investigated this problem for counter automata. We were able to show that the length of a shortest string accepted by an $n$-state (non-empty) counter automaton is at most $\Theta(n^2)$. See here: <https://lmcs.episciences.org/5251>

The lower bound can be obtained similar to how you described in your question with cycles of length $p$ and $q$ (or any two relatively prime numbers).

---

**Pushdown Automata**

*Upper Bound:* We can get an upper bound using standard techniques. The length of a shortest string accepted by an $n$-state (non-empty) pushdown automaton is at most $2^{O(n^2)}$.

Essentially, we argue that if the pushdown automaton's language is non-empty, then there exists some string that it accepts where the stack height is at most $O(n^2)$. Therefore, there are at most $n \cdot 2^{O(n^2)}$ (which is still $2^{O(n^2)}$) possible configurations so there must be an accepted string of length at most $2^{O(n^2)}$.

*Lower Bound:* For an exponential lower bound, see Jeffrey's answer above.

Also, see my answer to this related question: [Shortest string in the intersection of a context-free language and a regular language](https://cstheory.stackexchange.com/questions/37492/shortest-string-in-the-intersection-of-a-context-free-language-and-a-regular-lan/37502#37502)

This related answer leads to a deterministic binary stack (non-empty) PDA with an exponential lower bound for the length of a shortest accepted string. Note that the construction relies on the fact that logspace bounded auxiliary pushdown automata can run for exponential time.

For example, such a machine could iterate through the numbers from $0$ to $2^n - 1$ in binary on the stack using only $O(\log(n))$ auxiliary space.

---

**Update: A Tight Bound**

Due to results from [1] (Theorems 3.19 and 4.22), it follows that there is a tight bound. That is, the length of a shortest string accepted by an $n$-state (non-empty) pushdown automaton is at most $2^{\Theta\left(\frac{n^2}{\log(n)}\right)}$. This assumes a restriction on the PDA's such that the stack alphabet is fixed and the stack pushes or pops only one symbol at a time.

After looking through the proofs of Theorems 3.19 and 4.22, as far as I can tell, this result should hold for both deterministic and non-deterministic PDA's.

*Note:* I find their proofs difficult to fully verify / reconstruct. Does anyone know of a simplified argument? If not, I would always be interested in looking through this further with others.

---

**How To Apply Results From [1]**

*Rational Index:* The rational index of a language $L$ is a function $r$ such that for every $n$, $r(n)$ is the maximum length of a shortest string in $L \cap L(A)$ over all $n$-state non-deterministic finite automata $A$. In other words, $r(n) := max\_{A}\{ \; min\_{x}\{ \; \vert x \vert \; : \; x \in L \cap L(A) \; \} \; \}$ where $A$ is an $n$-state NFA and $x$ is a finite string. A definition for rational index can also be found in [2].

*Lower Bound:* By Theorem 3.19 from [1], we get an $2^{\Omega\left(\frac{n^2}{\log(n)}\right)}$ lower bound. This is because there is some fixed context-free language $L$ whose rational index is $2^{\Omega\left(\frac{n^2}{\log(n)}\right)}$.

Let me explain. Let $P$ denote a PDA that recognizes $L$. By the preceding, there is an infinite family $\{ A\_n \}\_{n \in \mathbb{N}}$ of finite automata such that for all $n$, $A\_n$ has $n$ states and asymptotically a shortest string accepted by the Cartesian product of $A\_n$ with $P$ has length $2^{\Omega\left(\frac{n^2}{\log(n)}\right)}$.

It looks to me that, each finite automaton $A\_n$ from their construction is deterministic. Also, the PDA $P$ is deterministic with a fixed stack alphabet that only pushes or pops one symbol at a time. Therefore, the lower bound applies to deterministic PDA's with a fixed stack alphabet that only push or pop one symbol at a time.

*Upper Bound:* By Theorem 4.22 from [1], we get an $2^{O\left(\frac{n^2}{\log(n)}\right)}$ upper bound. This is because any given context-free language has rational index $2^{O\left(\frac{n^2}{\log(n)}\right)}$.

Let me explain. Given any $n$-state PDA $P$ over a fixed alphabet that only pushes or pops one symbol at a time, we can convert it into an associated $O(n)$-state visibly pushdown automaton $P^{\prime}$ over a larger alphabet that must read a push-$c$ symbol in order to push $c$ onto the stack and a pop-$c$ symbol in order to pop $c$ off of the stack for each stack symbol $c$. The PDA's $P$ and $P^{\prime}$ have shortest accepted strings of similar length.

We can now view $P^{\prime}$ as the Cartesian product of a fixed PDA and an $O(n)$-state finite automaton. The fixed PDA's language has rational index $2^{O\left(\frac{n^2}{\log(n)}\right)}$ meaning that a shortest string accepted by $P^{\prime}$ has length at most $2^{O\left(\frac{n^2}{\log(n)}\right)}$. Therefore, a shortest string accepted by $P$ has length at most $2^{O\left(\frac{n^2}{\log(n)}\right)}$.

---

**References**

[1] *Pierre, Laurent*, [**Rational indexes of generators of the cone of context-free languages**](http://dx.doi.org/10.1016/0304-3975(92)90269-L), Theor. Comput. Sci. 95, No. 2, 279-305 (1992). [ZBL0745.68068](https://zbmath.org/?q=an:0745.68068).

[2] *Deleage, Jean-Luc; Pierre, Laurent*, [**The rational index of the Dyck language (D\_ 1^{’\*})**](http://dx.doi.org/10.1016/0304-3975(86)90158-1), Theor. Comput. Sci. 47, 335-343 (1986). [ZBL0632.68072](https://zbmath.org/?q=an:0632.68072).


---

### Answer by username_3 on 2019-11-24. Score: 9

The *precise* answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman). And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols. For example, a classic construction turns a grammar like

$S \rightarrow X\_1 X\_1$

$X\_1 \rightarrow X\_2 X\_2$

$X\_2 \rightarrow X\_3 X\_3$

...

$X\_{n-1} \rightarrow X\_n X\_n$

$X\_n \rightarrow a$

into a 3-state machine accepting the language $\{\,a^{2^n}\,\}$ by final state, no matter how many variables there are, or into a 1-state machine accepting by empty stack. This gives a classic example of how the shortest string can be exponential in the description size of the PDA.

> **Comments:**
> **username_0**: Could you please explain this "classic construction"? I can't find anything about it online.  
> **username_4**: Naturally, most of the classic proofs are not online (at least not the original version). I found that the proof of Theorem 5.4.1 in M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978 (the "pumping lemmings book") contains the construction of a 1-state pda accepting with empty stack. Its stack alphabet is identical to the variables of the grammar. I warmly recommend working through this book - it discusses several descriptional complexity questions like the one you asked.  
> **username_4**: Ah yes- and Jeffrey's answer refers to nondeterministic  PDAs, which was not exactly what you were asking for.  

---

### Answer by username_0 on 2019-11-23. Score: 7

(Answer inspired by Lamine's comment)

We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack alphabet of size $k$, we can construct an automaton that accepts a word of length $O(n^{k+c})$.

The basic idea is to just make the stack as large as possible, and then accept a unary word of that length. If we have stack symbols $a\_1, a\_2, \dots, a\_k$, we can construct the automaton as follows:

If the top symbol is $a\_k$, pop it and transition to a sequence of $n/k$ states that each accept a character of input. Otherwise, if the top of the stack is $a\_i$, pop it and transition to a sequence of $n/k$ states which pushes $n/k$ copies of $a\_{i+1}$ onto the stack. This results in accepting a single word of length $O((n/k)^k)$.

Edit: It turns out that you can simulate $k$ stack symbols using only $2$ stack symbols, by using a $\log(k)$ depth tree of states to "pop" symbols from the stack and a sequence of $\log(k)$ sequence of states to "push" symbols onto the stack. This means that with only two stack symbols, you can still have a minimum word that is nearly exponential in $n$.

> **Comments:**
> **username_1**: I don't understand why the stack alphabet should be in $\Omega(N)$. The conversion between a CFG and a PDA preserves the input alphabet size, which is the same as the stack alphabet. See the conversion algorithm in "Introduction to automata theory, languages and computation" by Hopcroft et al.  
> **username_1**: Moreover, you can convert your solution giving a word of length $\Omega(n/k)^k$ into a solution giving a word of length $\Omega(\sqrt{n}3^{\Omega(\sqrt{n})})$ by "emulating" each terminal $a_i$ $(1\leq i\leq k)$ by a subword $ab^i a$ and slightly transforming the PDA. You get a solution with superpolynomial length and only two protocols.  
> **username_1**: However, one has to check if the new construction is still deterministic.  
> **username_0**: @Lamine I just realized that you don't even need the unary encoding you proposed. You can just use a binary encoding to simulate a stack alphabet of size $k$ using $log(k)$ symbols from a 2-symbol alphabet with a corresponding $log(k)$ blowup in state size when writing to the stack and $k$ blowup when reading from the stack. This results in a nearly exponential solution.  

---

