Demonstrate that DPDA is closed under complement by construction

Question

I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I got has something that at the end does not fit. Could you give me a hand?

The main problem happens with the ε-moves. A PDA could finish reading its input in a non-final (rejecting state) but can still move to a final (accepting) state through an ε-move and end up accepting the string. This means that just adding a dead state and complementing the states does not work. I already solved the problem of possible infinite sequences of ε-moves, so that is not a main part of my question.

EDIT: As far as I understand, if the DPDA reaches end of input and is in an accepting state and moves to a rejecting state through an ε-move it would still accept it (as it reached a final state with no input symbol left to read).

Please let me know if I can be more clear.

Answer 1

I didn't have time to write this before but I found an answer. Here is what I did:

Let $O$ be the original $PDA$. We will construct a new $PDA$, call it $M$ ($M$ stands for modified).

To find the complement of $O$, we can flip final states to be non-final states and vice-versa. It is the same procedure as for finite automatas. However, there is a subtlety. The main problem is that in the original PDA $O$ the input $w$ can lead to a state $S$ which is not a final state but could perform an $\epsilon-move$ and get to an accepting state $S'$. Flipping states as mentioned above, would make $M$ end in $S$ with the input $w$ which would be a final state (causing $M$ to accept accept the input) even though it will later make an $\epsilon-move$ to $S'$, a non-accepting state. Therefore, both $O$ and $M$ will accept $w$. Something similar happens if $S$ was a final state and $S'$ a non-final state reachable from $S$ through an $\epsilon-move$.

In order to overcome this problem, we must make sure that all $\epsilon$-moves happen before we read the next symbol. That is, we will enter a reading state only when a path of $\epsilon$-moves is followed and we reach a state which has no $\epsilon$-move available. We call these latter states reading states, as they need an actual symbol to perform a new transition.

Define $M$'s states to be tuples of the form $<q, n>$ where $q \in Q$ ($Q$ is the set of states of the original $PDA$) and $n \in \{1, 2, 3, 4\}$.

• If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$ if $q \in F_O$.

• If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$ in $M$ if $q \notin F_O$.

• If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$.

• If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$ in $M$

• If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$ in $M$

In those definitions, we let states of the form $<q, 2>$ and $<q, 3>$ consume $\epsilon$-moves imitating $\epsilon$-moves of $O$ until there are no more. Then, perform an $\epsilon$-move to a reading state. Now for the reading states,

• If $\delta(q, a, X) = <q', \alpha>$ in $O$, let $\delta(<q, 1>, a, X) = \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$ in $M$.

By making this definition, we consume a symbol of the input and move to a state of the form $<q, 3>$ to begin a new series of $\epsilon$-moves.

Finally, make states of the form $<q, 4>$ be accepting states of $M$ if $q \notin F_O$. Also, make $<q_0, 3>$ the initial state of $M$ if $q_0$ is the initial state of $O$.

---

What we did is the following:

Create 4 "floors" of states (the second element of the tuple in states of $M$ determines in which floor we are). Floor 3 imitates $\epsilon$-moves of $O$ possibly reaching an accepting state $q$ of $O$. If that is the case, we move to floor 2; otherwise, we remain in floor 3. When there are no more $\epsilon$-moves to follow of $O$, we define $\epsilon$-moves of $M$ to reach a reading state. Floors 1 and 4 correspond to reading states. If we were on floor 3, we go to floor 4. If we were in floor 2, we reach floor 1. Only states $<q, 4>$ (states that are in floor 4) are accepting states of $M$, provided that $q$ is not an accepting state of $O$.

Please let me know if I made a typo at writing this. I could've easily mistaken. Also, my English is not very good so feel free to edit and rephrase things better.

Answer 2

There is a proof by construction in Sipser's Introduction to the Theory of Computation (3$^{rd}$ edition has a section on DCFLs) that identifies reading states of the automaton by splitting up any state that reads and pops at once. Only these reading states can be final states, and to get the complement DPDA you only reverse accepting behavior within the set of reading states.

Answer 3

You can assume the automaton to be free of $\varepsilon$-transitions without loss of generality.

This can be shown by using the standard construction from CFG to PDA applied to a Greibach normal form. In Silent Transitions in Automata with Storage, G. Zetzsche has recently presented a construction directly on automata.

Potential caveat: I kind of assume that said standard construction yields a DPDA if we apply it to a suitable, i.e. "deterministic", grammar and that this suitability survives transformation in Greibach normal form.