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$
$\endgroup$
1
-
$\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. ♦Commented May 17, 2017 at 17:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
- Convert $\langle M \rangle$ to the description of an equivalent CFG $\langle G \rangle $
- Check if $L(G)$ is infinite
- If yes, then answer yes else answer no
-
$\begingroup$ But as I know, the Pumping Lemma also works on finite context-free language? $\endgroup$ Commented May 17, 2017 at 5:48
-
$\begingroup$ @user7370059 Yes. But it only implies the result for an infinite language. I've edited the answer to clarify. $\endgroup$ Commented May 17, 2017 at 11:41