10
$\begingroup$

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?

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

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

Improve this answer
$\endgroup$
  • $\begingroup$ I also think that transformation PDA $\rightarrow$ CFG is polynomial. Thanks! So the problem is in $P$. $\endgroup$ – Lamine Jan 21 '11 at 13:34
  • $\begingroup$ 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. $\endgroup$ – Lamine Jan 24 '11 at 13:44
  • $\begingroup$ You're right, it actually doesn't matter. $\endgroup$ – Yuval Filmus Jan 24 '11 at 22:10
5
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lamine Jan 20 '11 at 15:12
  • 5
    $\begingroup$ Shoudn't this answer be a comment? $\endgroup$ – Oleksandr Bondarenko Jan 20 '11 at 15:35
  • 2
    $\begingroup$ Yes it should. Sariel, could you either move this to a comment or provide an answer ? $\endgroup$ – Suresh Venkat Jan 20 '11 at 17:51
  • $\begingroup$ @Suresh: You may be aware of this, but now moderators can turn an answer into a comment. $\endgroup$ – Tsuyoshi Ito Jan 21 '11 at 0:34
  • $\begingroup$ I moved the original answer to a comment. This is a new answer. $\endgroup$ – Suresh Venkat Jan 21 '11 at 8:18
0
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ (but definitely poly-time!) $\endgroup$ – alpoge Jan 20 '11 at 16:01
  • $\begingroup$ 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. $\endgroup$ – Lamine Jan 20 '11 at 16:12
  • $\begingroup$ Emptiness testing for CFLs is decidable, no? $\endgroup$ – alpoge Jan 20 '11 at 16:21
  • $\begingroup$ (Forgive me again if I am misunderstanding!) $\endgroup$ – alpoge Jan 20 '11 at 16:21
  • $\begingroup$ 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!). $\endgroup$ – alpoge Jan 20 '11 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.