[Solved]: Non Deterministic PDA accepted language not clear

Problem Detail: 

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?

Asked By : user3241846

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28739

 Ask a Question

 Download Related Notes/Documents