Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Problem statement :

Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?

Is this problem NP-complete? Has it been studied? Is there an algorithm allowing to find such a word?

• Shouldn't Djikstra's algorithm do the trick? (I am most probably misunderstanding something here!) Jan 20, 2011 at 15:26
• "length at most $k$"? Jan 20, 2011 at 15:50
• You're welcome, Kaveh. Yes, I forgot "at most", I edited again. Jan 20, 2011 at 15:57
• The answer is easy - is this a homework question? Jan 21, 2011 at 0:36
• Do we have access to the automatons description or do we only have it as black box? Jan 21, 2011 at 17:32

Compute the intersection of your CFG language with the regular language $\sum_{i=0}^k A^k$ (this amounts to multiplying the number of states by $k$ and adding a "dead end" state). Now check whether the result is empty: convert into a grammar (I think the result will have polynomial size) and "backtrack" from epsilon productions.

Edit: Kaveh mentioned that this is polynomial in $k$, so if $k$ is given as an input, the algorithm is exponential in $|k|$. However, Kaveh found a way to fix it. Convert the original automaton to a CFG, and replace all terminals by a fixed terminal. Now use an iterative algorithm to find the minimal size of a word generated by each non-terminal, as follows.

Initialize all lengths with $\infty$, and then iteratively update all lengths in the obvious way: given a production $A \rightarrow a^t \prod B_i$ (the order doesn't matter), put $f(A) = \min(f(A),t+\sum f(B_i))$. Claim: this converges in $O(n)$ iterations, where $n$ is the number of non-terminals. The reason is that in a tree generating the minimal-length word, no non-terminal is used twice; each "edge" takes at most one iteration to process (some edges can be "updated" in parallel).

• I also think that transformation PDA $\rightarrow$ CFG is polynomial. Thanks! So the problem is in $P$. Jan 21, 2011 at 13:34
• Ok, since there is a way to compute directly the lowest length, $|k|$ is not an input. But I don't understand why replacing all terminals by a fixed one. The algorithm should operate correctly with original terminals. Jan 24, 2011 at 13:44
• You're right, it actually doesn't matter. Jan 24, 2011 at 22:10

Change all the alphabet characters to a single specific character. Now, you have PDA defined over a single character. Its language is a context-free grammar. However, context free grammar over a single character is regular. So, convert the CFG into a regular language, and then check if it contains a word of length k.

Now, all these conversions tends to require exponential time, but it seems to me unlikely that the problem is NP complete. Especially if you allow polynomial time in $k$.

I might be wrong, and I apologize for my initial snippy answer...

BTW, the fact that a CFG over a single letter is regular follows from Parikh's theorem. Although a direct proof is not too hard. See the link for more details on Parikh's theorem - it is a beautiful result... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

• No, I'm not student. The problem I mentioned is initially a network problem that a modeled as an automaton one. I would just know if it's worth to look for a polynomial solution or not. Jan 20, 2011 at 15:12
• Shoudn't this answer be a comment? Jan 20, 2011 at 15:35
• Yes it should. Sariel, could you either move this to a comment or provide an answer ? Jan 20, 2011 at 17:51
• @Suresh: You may be aware of this, but now moderators can turn an answer into a comment. Jan 21, 2011 at 0:34
• I moved the original answer to a comment. This is a new answer. Jan 21, 2011 at 8:18

A probably suboptimal method: Run Djikstra's algorithm. Then, for each final state, compare the distances with $k$. If any are $\leq k$, accept. Reject.

EDIT: The above only works for NFAs! Sorry about that.

• (but definitely poly-time!) Jan 20, 2011 at 16:01
• I'm not sure that Dijkstra's algorithm can resolve the problem. It can find the shortest path between the initial state and final ones. Of course, a word which can be accepted through this paths can be generated. But this paths are elementary, and words can be accepted through nonelementary paths; otherwise the problem of determining if a context-free grammar can generate any word would be decidable, but it is not. Jan 20, 2011 at 16:12
• Emptiness testing for CFLs is decidable, no? Jan 20, 2011 at 16:21
• (Forgive me again if I am misunderstanding!) Jan 20, 2011 at 16:21
• Well, one can use a 'marking' algorithm to do this (given the CFG)--marking terminals, then marking things that derive terminals, then marking things that derived things that are marked, etc. until the process terminates, and then checking if the start variable is marked. Also, ignore my answer--that's what you should do for an NFA (certainly not for a PDA!). Jan 20, 2011 at 19:51