# Is there an algorithm that given a PDA $M$ decides if there exists a string in $L(M)$ with a suitable decomposition?

I am looking for an algorithm that given a PDA $M$ decides whether there exists $w \in L(M)$ for which there exists a decomposition $w = uvxyz$ that satisfies $|vy| \geq 1$ and $uv^ixy^iz \in L(M)$ for every $i \geq 0$.

• It appears you may have created multiple accounts. I encourage you to merge them. Also, I encourage you to register your account so you can retain access to it. This will allow you to post comments under an answer requesting clarification. (Those comments should not be posted in the 'answer' box.) – D.W. May 17 '17 at 17:11

In a context-free language $L$, by the Pumping Lemma, there exists a $p > 0$ such that every $w \in L$ such that $|w| \ge p$ admits a decomposition $w = uvxyz$ such that $uv^ixy^iz \in L$ for all $i \geq 0$.

If $L$ is infinite, it has words of length $\ge p$, and you can pick any of them. If $L$ is finite then no word satisfies the condition (this is not a contradiction with the pumping lemma, because the pumping lemma gives a length $p$ which is more than the length of any of the words in $L$).

It is decidable if a context-free grammar generates an infinite language (see e.g. Is it decidable whether a given context free grammar generates an infinite number of strings?).

Therefore the algorithm is

On input $\langle M \rangle$, where $M$ is a PDA

1. Convert $\langle M \rangle$ to the description of an equivalent CFG $\langle G \rangle$
2. Check if $L(G)$ is infinite