I was asked the next question in my homework assignment: I just want to make sure that I fully understand what it is that's required of me. Am I asked to find an algorithm which decides if the language that's accepted by the PDA is finite? And if not, then what is it? Any initial intuition?

**I don't need help with answering it, just understanding the question. I'm asked to show an algorithm that given a PDA $A$ decides whether there exists a word $w$ that's accepted by the PDA for which there exists a decomposition $w=uvxyz$ that satisfies that the length of $vy$ is atleast 1 and $u(v^i)x(y^i)z$ is accepted by the PDA for every $i\ge0$.

  • $\begingroup$ I'm just trying to figure out what's the meaning behind the question.I cannot ask my lecturer that question $\endgroup$ – user121212 May 20 '17 at 7:54
  • $\begingroup$ Edited it, by request $\endgroup$ – user121212 May 20 '17 at 8:01
  • 1
    $\begingroup$ I think that the question is pretty clear. What you are really asking is whether the property you are supposed to decide is equivalent to the language being infinite. Have you tried proving this? $\endgroup$ – Yuval Filmus May 20 '17 at 10:06
  • $\begingroup$ Yes. I believe that if the language was finite then by the pumping lemma I could reach to an infinite language therefore I've written an algorithm for deciding whether the language is finite or not. It is correct? $\endgroup$ – user121212 May 20 '17 at 11:17
  • $\begingroup$ We don't grade homework on this site. It's your TA's job. You should be able to tell if your solution is correct or not. $\endgroup$ – Yuval Filmus May 20 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.