<p>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.</p>

<p>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$.</p>

<p>I might be wrong, and I apologize for my initial snippy answer...</p>

<p>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... <a href="http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf" rel="noreferrer">http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf</a></p>

CC BY-SA 2.5
2011-01-20T15:12:11.633Z
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.
Lamine
CC BY-SA 2.5
2011-01-20T15:35:54.577Z
Shoudn't this answer be a comment?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-20T17:51:25.490Z
Yes it should. Sariel, could you either move this to a comment or provide an answer ?
Suresh Venkat
CC BY-SA 2.5
2011-01-21T00:34:42.863Z
@Suresh: You may be aware of this, but now [moderators can turn an answer into a comment](http://meta.stackexchange.com/questions/35175/should-moderators-be-able-to-convert-answers-into-comments/74160#74160).
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-21T08:18:50.500Z
I moved the original answer to a comment. This is a new answer.
Suresh Venkat
CC BY-SA 2.5
2011-01-20T15:01:28.980Z
2011-01-21T03:13:16.427Z
2011-01-21T03:13:16.427Z
Sariel Har-Peled
<p><s>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.</s></p>

<p>EDIT: The above only works for NFAs! Sorry about that.</p>

CC BY-SA 2.5
2011-01-20T16:01:12.683Z
(but definitely poly-time!)
alpoge
CC BY-SA 2.5
2011-01-20T16:12:18.963Z
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.
Lamine
CC BY-SA 2.5
2011-01-20T16:21:28.267Z
Emptiness testing for CFLs is decidable, no?
alpoge
CC BY-SA 2.5
2011-01-20T16:21:41.903Z
(Forgive me again if I am misunderstanding!)
alpoge
CC BY-SA 2.5
2011-01-20T19:51:47.593Z
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!).
alpoge
CC BY-SA 2.5
2011-01-20T15:49:39.293Z
2011-01-20T19:52:49.993Z
2011-01-20T19:52:49.993Z
alpoge
<p>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.</p>

<p>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.</p>

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

CC BY-SA 2.5
2011-01-21T13:34:16.613Z
I also think that transformation PDA $\rightarrow$ CFG is polynomial. Thanks! So the problem is in $P$.
Lamine
CC BY-SA 2.5
2011-01-24T13:44:44.343Z
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.
Lamine
CC BY-SA 2.5
2011-01-24T22:10:20.573Z
You're right, it actually doesn't matter.
Yuval Filmus
CC BY-SA 2.5
2011-01-21T04:23:01.330Z
2011-01-21T18:30:48.103Z
2011-01-21T18:30:48.103Z
Yuval Filmus
<p>Problem statement :</p>

<p>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$ ?</p>

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

CC BY-SA 2.5
2011-01-20T15:26:11.513Z
Shouldn't Djikstra's algorithm do the trick? (I am most probably misunderstanding something here!)
alpoge
CC BY-SA 2.5
2011-01-20T15:50:35.407Z
"length at most $k$"?
alpoge
CC BY-SA 2.5
2011-01-20T15:57:37.710Z
You're welcome, Kaveh. Yes, I forgot "at most", I edited again.
Lamine
CC BY-SA 2.5
2011-01-21T00:36:03.900Z
The answer is easy - is this a homework question?
Sariel Har-Peled
CC BY-SA 2.5
2011-01-21T17:32:35.667Z
Do we have access to the automatons description or do we only have it as black box?
Raphael
<cc.complexity-theory><np-hardness><fl.formal-languages><automata-theory>
Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton
Lamine
# Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

(Asked by: username_0 on 2011-01-20)

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?

**Tags:** cc.complexity-theory, np-hardness, fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: Shouldn't Djikstra's algorithm do the trick? (I am most probably misunderstanding something here!)  
> **username_1**: "length at most $k$"?  
> **username_0**: You're welcome, Kaveh. Yes, I forgot "at most", I edited again.  
> **username_2**: The answer is easy - is this a homework question?  
> **username_3**: Do we have access to the automatons description or do we only have it as black box?  

---

## 3 answers

### Answer by username_7 on 2011-01-21. Score: 9 | Accepted answer

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

> **Comments:**
> **username_0**: I also think that transformation PDA $\rightarrow$ CFG is polynomial. Thanks! So the problem is in $P$.  
> **username_0**: 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.  
> **username_7**: You're right, it actually doesn't matter.  

---

### Answer by username_2 on 2011-01-20. Score: 5

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>

> **Comments:**
> **username_0**: 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.  
> **username_4**: Shoudn't this answer be a comment?  
> **username_5**: Yes it should. Sariel, could you either move this to a comment or provide an answer ?  
> **username_6**: @Suresh: You may be aware of this, but now [moderators can turn an answer into a comment](http://meta.stackexchange.com/questions/35175/should-moderators-be-able-to-convert-answers-into-comments/74160#74160).  
> **username_5**: I moved the original answer to a comment. This is a new answer.  

---

### Answer by username_1 on 2011-01-20. Score: 0

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

> **Comments:**
> **username_1**: (but definitely poly-time!)  
> **username_0**: 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.  
> **username_1**: Emptiness testing for CFLs is decidable, no?  
> **username_1**: (Forgive me again if I am misunderstanding!)  
> **username_1**: 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!).  

---

