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.
Demonstrate that DPDA is closed under complement by construction
formal languages;automata;closure properties;pushdown automata