Shortest word accepted by a PDA

Question

Given a 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?

Answer 1

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.