1
$\begingroup$

This is a PDA from the lecture slides I'm using:

They say it accepts all words that contain double a's. While it makes some sense it's not full proof.

What prevents the second a to be read in the left branch not the right? Or even a 3rd..4th a and so on? Is that the case of human Intervention like needed in PDA for oddpalindrome?

Also as far as I understand a PDA needs to read the whole input tape AND have an empty stack by the end which doesnt seem to be the case if the input is more than an a. What am I not understanding?

$\endgroup$
  • $\begingroup$ You should include the picture here. $\endgroup$ – Yuval Filmus Jul 27 '14 at 2:53
  • 1
    $\begingroup$ @YuvalFilmus You can edit, you know. $\endgroup$ – Raphael Jul 27 '14 at 7:24
  • 2
    $\begingroup$ This image does not seem to show a PDA as it's usually represented. You can check your understanding by translating it into the more common state machine form! Then, what do you mean by "human interference"? I think you have to check the definition of PDAs and their accepted language again. Regarding acceptance criterion, there are several, equivalent ones. $\endgroup$ – Raphael Jul 27 '14 at 7:26
  • 1
    $\begingroup$ Also, I don't understand your language "definition". " all words that contain double a's" sounds very regular to me, namely $\Sigma^* aa \Sigma^*$. $\endgroup$ – Raphael Jul 27 '14 at 7:28
  • $\begingroup$ @Raphael Yes, the stated language is regular but every regular language is accepted by some PDA so that needn't be a problem. $\endgroup$ – David Richerby Jul 27 '14 at 8:27
2
$\begingroup$

The PDA you're linking to is non-deterministic; indeed, the state you are confused about has two out-edges labeled $a$. For the PDA to accept its string, it's enough for there to be one accepting computation – what you refer to inaccurately as "human interference" [intervention?]. Regarding the acceptance condition of the PDA, figure out what acceptance condition makes this PDA accept the advertised language, and this is the accepting condition that you should have in mind.

$\endgroup$
  • $\begingroup$ Yes I meant intervention. By one accepting computation im assuming you mean the program already ran in one "a" loop right before the current run? Also do you check for the accepting computation using the stack? $\endgroup$ – user3241846 Jul 27 '14 at 14:06
  • $\begingroup$ I suggest you review the definition of nondeterministic PDAs. This will answer all your questions. $\endgroup$ – Yuval Filmus Jul 28 '14 at 13:10
  • $\begingroup$ In the very paper in which Turing introduced the Turing machine, he also introduced nondeterminism. He motivated it by the act of guiding a machine by human intervention. I guess that user3241846's source still motivates it like that as well even though it seems a little outdated. $\endgroup$ – Oliver Witt Aug 27 '14 at 7:48

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.