Maximum shortest word accepted by pushdown automata 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)$.
The precise 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

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