Why "The DPDA may accept its input by entering both accept and non-accept states in a sequence of moves at the end of the input string. "

Question

In book "Introduction to the Theory of Computation" by M. Sipser.
Captioned statement claimed in proof idea of theorem 2.42: "The class of DCFLs is closed under complementation."

My understanding is that DPDA means that all transitions are deterministic, how DPDA can go to both accept state & non-accept state after all input read out?

Answer 1

It may help to think of an input word as an infinite sequence of letters, which is eventually a special "after the end of the input" character. Instead of $ababab$, think $ababab\#\#\#\#\#\ldots$

Depending on the specific definition of pushdown automaton you're using, the pushdown automaton is allowed to continue reading in these "after the end of the input" characters until it has used up its stack, at which point it accepts or rejects depending on the state it's in when it uses up its stack.

Answer 2

According to book "Introduction to the Theory of Computation", p131, "If a DPDA enters an accept state after it has read the last input symbol of an input string, it accepts that string. In all other cases, it rejects that string.".

So even the string was already accepted, the corresponding DPDA could still move on with $\varepsilon$ input, which made the automate pass some other states. And some other states are the states mentioned in "entering both accept and non-accept states in a sequence of moves at the end of the input string.".