Demostrar que DPDA está cerrado bajo el complemento por construcción

He estado intentando durante bastante tiempo encontrar una construcción para poder demostrar formalmente que un PDA determinista está cerrado bajo complementación. Sin embargo, sucede que cada idea que tengo tiene algo que al final no encaja. ¿Me puedes dar una mano?

El principal problema ocurre con los movimientos ε . Un PDA podría terminar de leer su entrada en un estado no final (estado de rechazo) pero aún puede pasar a un estado final (aceptar) a través de un movimiento ε y terminar aceptando la cadena. Esto significa que simplemente agregar un estado muerto y complementar los estados no funciona. Ya resolví el problema de posibles secuencias infinitas de movimientos ε , por lo que esa no es una parte principal de mi pregunta.

EDITAR: Por lo que yo entiendo, si el DPDA llega al final de la entrada y está en un estado de aceptación y se mueve a un estado de rechazo a través de un movimiento ε , todavía lo aceptaría (ya que alcanzó un estado final sin símbolo de entrada a la izquierda) leer).

Avísame si puedo ser más claro.

No tuve tiempo de escribir esto antes, pero encontré una respuesta. Aquí esta lo que hice:

Deje que sea ​​el original . Construiremos un nuevo , llámelo ( significa modificado).$O$$PDA$$PDA$$M$$M$

Para encontrar el complemento de , podemos cambiar los estados finales para que sean estados no finales y viceversa. Es el mismo procedimiento que para los autómatas finitos. Sin embargo, hay una sutileza. El principal problema es que en el PDA original, la entrada puede conducir a un estado que no es un estado final pero que puede realizar un y llegar a un estado de aceptación . Cambiar los estados como se mencionó anteriormente, haría que terminara en con la entrada que sería un estado final (haciendo que acepte aceptar la entrada) a pesar de que más tarde se moverá a$O$$O$$w$$S$$\epsilon-move$$S'$$M$$S$$w$$M$$\epsilon-move$$S'$, un estado de no aceptación. Por lo tanto, tanto como aceptarán . Algo similar sucede si era un estado final y un estado no final accesible desde través de un .$O$$M$$w$$S$$S'$$S$$\epsilon-move$

Para superar este problema, debemos asegurarnos de que todos los movimientos sucedan antes de leer el siguiente símbolo. Es decir, entraremos en un estado de lectura solo cuando se siga una ruta de -moves y lleguemos a un estado que no tenga -move disponible. Llamamos a estos últimos estados estados de lectura , ya que necesitan un símbolo real para realizar una nueva transición.$\epsilon$$\epsilon$$\epsilon$

Defina los estados de como tuplas de la forma donde ( es el conjunto de estados del original ) y .$M$$<q, n>$$q \in Q$$Q$$PDA$$n \in \{1, 2, 3, 4\}$

• Si en , deje en si .$\delta(q, \epsilon, X) = <q', \alpha>$$O$$\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$$M$$q \in F_O$

• Si en , deje en si .$\delta(q, \epsilon, X) = <q', \alpha>$$O$$\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$$M$$q \notin F_O$

• Si en , deje en .$\delta(q, \epsilon, X) = <q', \alpha>$$O$$\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$$M$

• Si está en , en$\delta(q, \epsilon, X)$$undefined$$O$$\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$$M$

• Si está en , en$\delta(q, \epsilon, X)$$undefined$$O$$\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$$M$

En esas definiciones, dejamos que los estados de la forma y consuman -moves imitando -moves de hasta que no haya más. Luego, realice un -move a un estado de lectura. Ahora para los estados de lectura,$<q, 2>$$<q, 3>$$\epsilon$$\epsilon$$O$$\epsilon$

• Si en , deje en .$\delta(q, a, X) = <q', \alpha>$$O$$\delta(<q, 1>, a, X) = \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$$M$

Al hacer esta definición, consumimos un símbolo de la entrada y pasamos a un estado de la forma para comenzar una nueva serie de movimientos .$<q, 3>$$\epsilon$

Finalmente, haga que los estados de la forma acepten estados de si . También, make el estado inicial de si es el estado inicial de .$<q, 4>$$M$$q \notin F_O$$<q_0, 3>$$M$$q_0$$O$

Lo que hicimos es lo siguiente:

Cree 4 "pisos" de estados (el segundo elemento de la tupla en estados de determina en qué piso estamos). Planta 3 imita -moves de , posiblemente, llegar a un estado de aceptación de . Si ese es el caso, pasamos al piso 2; de lo contrario, permanecemos en el piso 3. Cuando no hay más movimientos de , definimos movimientos de para alcanzar un estado de lectura. Los pisos 1 y 4 corresponden a estados de lectura. Si estábamos en el piso 3, pasamos al piso 4. Si estábamos en el piso 2, llegamos al piso 1. Solo los estados (estados que están en el piso 4) aceptan estados de$M$$\epsilon$$O$$q$$O$$\epsilon$$O$$\epsilon$$M$$<q, 4>$$M$ , siempre que no es un estado de aceptación de .$q$$O$

Por favor, avíseme si cometí un error al escribir esto. Podría haberme equivocado fácilmente. Además, mi inglés no es muy bueno, así que siéntete libre de editar y reformular mejor las cosas.

Hay una prueba por construcción en la Introducción a la teoría de la computación de Sipser (la edición 3 tiene una sección sobre DCFL) que identifica los estados de lectura del autómata al dividir cualquier estado que se lee y aparece a la vez. Solo estos estados de lectura pueden ser estados finales, y para obtener el DPDA complementario solo se invierte el comportamiento de aceptación dentro del conjunto de estados de lectura.$^{rd}$

Puede suponer que el autómata está libre de transiciones sin pérdida de generalidad.$\varepsilon$

Esto se puede mostrar utilizando la construcción estándar de CFG a PDA aplicada a una forma normal de Greibach . En Transiciones silenciosas en autómatas con almacenamiento , G. Zetzsche ha presentado recientemente una construcción directamente en autómatas.

Advertencia potencial: supongo que dicha construcción estándar produce un DPDA si lo aplicamos a una gramática adecuada, es decir, "determinista", y que esta idoneidad sobrevive a la transformación en forma normal de Greibach.