I'm having problem understanding the first part of this proof. I don't understand why it needs to hang at $(p,\epsilon,\epsilon)$ why can't the automaton just keep going, just reading the rest of the characters without touching the stack? For example what if I have a DPDA that always keeps its stack empty? like, it only reads characters, but doesn't alter the stack. taking $(q_0,a,\epsilon)$ and returning $(q_0,\epsilon)$ every time. Is it because it necessarily needs to do something when given $\epsilon$ as input? In that case can't I just say that if I read $\epsilon$ I return the empty set? Here's the definition I was given of DPDA.
Here's the definition given in Sipser's book
I don't see from these definitions why I shouldn't be able to define a DPDA that has a single state $q_0$ and just reads the whole input without ever touching the stack, like this: $\delta(q_0,a,\epsilon)=(q_0,\epsilon)$ $\forall a\in\Sigma$

enter image description here

  • 1
    $\begingroup$ I am sure that on an earlier slide, your lecturer will have a definition for (D)PDAs that requires a symbol from the stack in each transition. This is kind of the idea behind this alternative acceptance-by-empty-stack condition: The automaton cannot move further and will accept the word that has been processed up to that point of the run. $\endgroup$
    – ttnick
    Commented May 21 at 10:08
  • $\begingroup$ @ttnick I mean not exactly, at least I don't see it: imgur.com/a/CM3NRCq Here the delta transition function is supposed to be the same as the one a non-deterministic pda uses, so it can receive $(q_0,a,\epsilon)$ as input. Here's an alternative definition given in Sipser's book: imgur.com/a/JuNTplC $\endgroup$
    – lazyelekid
    Commented May 21 at 17:25
  • 1
    $\begingroup$ You're not showing their definition of PDAs, but this text is clear: X is a symbol of the stack alphabet, it cannot be empty. $\endgroup$ Commented May 22 at 22:18
  • 1
    $\begingroup$ As remarked by @reinierpost, the symbol $X\in \Gamma$ in the definition from the slides indicates that every instruction of a PDA reads the topmost symbol of the stack. This is rather standard. The book of Sipser on the other hand uses a different model: the PDA may ignore the stack, hence $\Gamma_\varepsilon$. That allows Sipser to happily compute on empty stack as you observe. The standard model (which is used in the slide with the Theorem) does not allow this. Better not mix definitions. $\endgroup$ Commented May 24 at 23:46
  • $\begingroup$ I was hoping it wasn't necessary to clarify this again, but it's the same model. Yes, the symbol $X$ can't be $\epsilon$ but the $\delta$ function can receive $\epsilon$ as a parameter, because it has the same domain as the function we use for the standard PA. The slides you're talking about have nothing to do with what $\delta$ can receive as input, they just specify what to do for specific inputs. $\endgroup$
    – lazyelekid
    Commented May 25 at 0:07

1 Answer 1


The problem was that a word will only be accepted by empty stack if it empties the stack just as I finish reading the word. That's why in the proof above we can't accept ww'. But the automata that I described are entirely possible going by the definitions.
It's perfectly legal to not read anything from the stack, in that case the automaton would act as an FDA.
So to sum it up, the automaton is allowed to keep going, not touching the stack, but then that word wouldn't be accepted by empty stack.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.