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$
5
  • $\begingroup$ Shouldn't Djikstra's algorithm do the trick? (I am most probably misunderstanding something here!) $\endgroup$
    – alpoge
    Jan 20, 2011 at 15:26
  • $\begingroup$ "length at most $k$"? $\endgroup$
    – alpoge
    Jan 20, 2011 at 15:50
  • $\begingroup$ You're welcome, Kaveh. Yes, I forgot "at most", I edited again. $\endgroup$
    – Lamine
    Jan 20, 2011 at 15:57
  • 1
    $\begingroup$ The answer is easy - is this a homework question? $\endgroup$
    – Sariel Har-Peled
    Jan 21, 2011 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, 2011 at 17:32

3 Answers 3

Reset to default
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$
3
  • $\begingroup$ I also think that transformation PDA $\rightarrow$ CFG is polynomial. Thanks! So the problem is in $P$. $\endgroup$
    – Lamine
    Jan 21, 2011 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, 2011 at 13:44
  • $\begingroup$ You're right, it actually doesn't matter. $\endgroup$
    – Yuval Filmus
    Jan 24, 2011 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$
5
  • $\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, 2011 at 15:12
  • 5
    $\begingroup$ Shoudn't this answer be a comment? $\endgroup$
    – Oleksandr Bondarenko
    Jan 20, 2011 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, 2011 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, 2011 at 0:34
  • $\begingroup$ I moved the original answer to a comment. This is a new answer. $\endgroup$
    – Suresh Venkat
    Jan 21, 2011 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$
5
  • $\begingroup$ (but definitely poly-time!) $\endgroup$
    – alpoge
    Jan 20, 2011 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, 2011 at 16:12
  • $\begingroup$ Emptiness testing for CFLs is decidable, no? $\endgroup$
    – alpoge
    Jan 20, 2011 at 16:21
  • $\begingroup$ (Forgive me again if I am misunderstanding!) $\endgroup$
    – alpoge
    Jan 20, 2011 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, 2011 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.