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

8

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.

PALEN
fuente
¿Supongo que está interesado en la propiedad de cierre de DCFL contra la complementación? Tu frase "formalmente demuestra que un PDA determinista está cerrado bajo complementación" tiene poco sentido para mí de lo contrario.
Raphael

Respuestas:

3

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).OPDAPDAMM

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á aOOwSϵmoveSMSwMϵmoveS, 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 .OMwSSSϵ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.ϵϵϵ

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

  • Si en , deje en si .δ(q,ϵ,X)=<q,α>Oδ(<q,3>,ϵ,X)=<<q,2>,α>MqFO

  • Si en , deje en si .δ(q,ϵ,X)=<q,α>Oδ(<q,3>,ϵ,X)=<<q,3>,α>MqFO

  • Si en , deje en .δ(q,ϵ,X)=<q,α>Oδ(<q,2>,ϵ,X)=<<q,2>,α>M

  • Si está en , enδ(q,ϵ,X)undefinedOδ(<q,2>,ϵ,X)=<<q,1>,X>M

  • Si está en , enδ(q,ϵ,X)undefinedOδ(<q,3>,ϵ,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>ϵϵOϵ

  • Si en , deje en .δ(q,a,X)=<q,α>Oδ(<q,1>,a,X)=δ(<q,4>,a,X)=<<q,3>,α>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>ϵ

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>MqFO<q0,3>Mq0O


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 deMϵOqOϵOϵM<q,4>M , siempre que no es un estado de aceptación de .qO

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.

PALEN
fuente
1

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

sjmc
fuente
-2

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

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.

Rafael
fuente
2
Lo sentimos, pero la suposición no se cumple. . {anbmcnm,n1}{anbmdmm,n1}
Hendrik Jan
@HendrikJan No entiendo de qué manera su idioma refuta mi suposición.
Raphael
Está libre de contexto determinista, pero necesita -transitions. Intuitivamente, uno necesita apilar tanto como dejar que la letra o decida cuál usar. Al leer tenemos que reventar todas las . εnmcdcb
Hendrik Jan
1
Es el ejemplo que sé que muestra DPDA "en tiempo real" no es una forma normal. (Para una prueba, debe comenzar una nueva pregunta :)) Una buena característica es que solo necesita -transitions que también resaltan la pila, evitando cálculos infinitos. ε
Hendrik Jan
3
Raphael, creo que @HendrikJan tiene razón. Eso no contradice la para PDA, porque la aplicación de este último a un DPDA introduce no determinismo. ε
Georg Zetzsche