Given a [pushdown automaton](https://en.wikipedia.org/wiki/Pushdown_automaton) (PDA), we seek a shortest word accepted by it. A standard approach is to map the problem in the corresponding context-free grammar. Can we analyze and solve this problem directly in the PDA?



Shortest word accepted by a PDA
I think you can just solve the "obvious inequalities" to get a polynomial time algorithm. I.e. assume acceptance by empty stack, and for each pair of states $p$, $q$ and a stack symbol $t$, let $T(p, q, t)$ be the minimal word length you need to move from state $p$ to $q$ while erasing $t$ from the stack, without dipping deeper into the stack than the symbol $t$.


There are some obvious inequalities:
$T(p, q, t) \leq c$ if there is a direct transition erasing $t$,
$T(p, q, t) \leq T(r, q', t') + T(q', q, t) + c$ if you have a transition of cost $c$ from state $p$ to state $r$ that writes $t'$ on stack, and
$T(p, q, t) \leq T(r, q, t) + c$ if you have a transition of cost $c$ from state $p$ to state $r$ that writes nothing on stack.


A maximal solution to these inequalities is easy to compute, start with infinite values for all $T(p, q, t)$ and propagate the information.
The number of steps is polynomial, and I think it's easy to see that the maximal solution $T'$ is the "actual truth" about $T(p, q, t)$, by induction on the length of the shortest number of transitions (possibly reading empty words) "realizing" the particular $T(p, q, t)$.


So you can now just take the minimum of $T(q\_0, q, t\_0)$ where $q\_0$ is the initial state and $t\_0$ the initial stack symbol.


