PDA accepting by empty stack

PDA accepting by empty stack

by ANDREA FELLINE -
Number of replies: 3

If a PDA accepts by empty stack, does that mean that there shouldn't be even Z0 in it?

I mean, we use Z0 to know when the stack is empty, but if the PDA accepts when the stack contais only Zthen it would also always accept on the initial state (when nothing has been pushed yet), and this would not make sense. Is this right?

In reply to ANDREA FELLINE

Re: PDA accepting by empty stack

by Giorgio Satta -

The PDA accepts when the stack is 100% empty, no \( Z_0 \) symbol in it.

You write that, if the PDA were to accept when \( Z_0 \) is on the top of the stack, then it would accept right at the beginning of the string ... that is not true: remember that the test for acceptance should be done only when you are at the end of the string.

In reply to Giorgio Satta

Re: PDA accepting by empty stack

by ANDREA FELLINE -
Thank you for clarifying.

But can't the PDA be used to test a string? If so, if I were to test the empty string and if it would accept when there is only Z0, then wouldn't the PDA always accept it?
In reply to ANDREA FELLINE

Re: PDA accepting by empty stack

by Giorgio Satta -

Yes, that is correct. If the automaton accepts on \( Z_0 \), then the empty string \( \varepsilon \) would always be accepted.