patternMinor
Demonstrate that DPDA is closed under complement by construction
Viewed 0 times
constructioncloseddemonstratedpdaunderthatcomplement
Problem
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.
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.
Solution
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 $$ 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) = $ in $O$, let $\delta(, \epsilon, X) = , \alpha>$ in $M$ if $q \in F_O$.
-
If $\delta(q, \epsilon, X) = $ in $O$, let $\delta(, \epsilon, X) = , \alpha>$ in $M$ if $q \notin F_O$.
-
If $\delta(q, \epsilon, X) = $ in $O$, let $\delta(, \epsilon, X) = , \alpha>$ in $M$.
-
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(, \epsilon, X) = , X>$ in $M$
-
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(, \epsilon, X) = , X>$ in $M$
In those definitions, we let states of the form $$ and $$ 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,
By making this definition, we consume a symbol of the input and move to a state of the form $$ to begin a new series of $\epsilon$-moves.
Finally, make states of the form $$ be accepting states of $M$ if $q \notin F_O$. Also, make $$ 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 $$ (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.
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 $$ 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) = $ in $O$, let $\delta(, \epsilon, X) = , \alpha>$ in $M$ if $q \in F_O$.
-
If $\delta(q, \epsilon, X) = $ in $O$, let $\delta(, \epsilon, X) = , \alpha>$ in $M$ if $q \notin F_O$.
-
If $\delta(q, \epsilon, X) = $ in $O$, let $\delta(, \epsilon, X) = , \alpha>$ in $M$.
-
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(, \epsilon, X) = , X>$ in $M$
-
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(, \epsilon, X) = , X>$ in $M$
In those definitions, we let states of the form $$ and $$ 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) = $ in $O$, let $\delta(, a, X) = \delta(, a, X) = , \alpha>$ in $M$.
By making this definition, we consume a symbol of the input and move to a state of the form $$ to begin a new series of $\epsilon$-moves.
Finally, make states of the form $$ be accepting states of $M$ if $q \notin F_O$. Also, make $$ 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 $$ (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.
Context
StackExchange Computer Science Q#18800, answer score: 5
Revisions (0)
No revisions yet.