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

  • $\begingroup$ 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.) $\endgroup$ – 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
  3. If yes, then answer yes else answer no
| cite | improve this answer | |
  • $\begingroup$ But as I know, the Pumping Lemma also works on finite context-free language? $\endgroup$ – user7370059 May 17 '17 at 5:48
  • $\begingroup$ @user7370059 Yes. But it only implies the result for an infinite language. I've edited the answer to clarify. $\endgroup$ – Gilles 'SO- stop being evil' May 17 '17 at 11:41

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.