Probar el cierre bajo la reversión de los idiomas aceptados por los autómatas min-heap

Esta es una pregunta de seguimiento de esta .

En una pregunta anterior sobre máquinas de estado exóticas , Alex ten Brink y Raphael abordaron las capacidades computacionales de un tipo peculiar de máquina de estados: los autómatas de min-montón. Pudieron demostrar que el conjunto de idiomas aceptados por tales máquinas ( ) no es un subconjunto ni un superconjunto del conjunto de lenguajes libres de contexto. Dada la resolución exitosa y el aparente interés en esa pregunta, procedo a hacer varias preguntas de seguimiento.$HAL$

Se sabe que los idiomas regulares están cerrados bajo una variedad de operaciones (podemos limitarnos a operaciones básicas como unión, intersección, complemento, diferencia, concatenación, estrella de Kleene e inversión), mientras que los idiomas libres de contexto tienen un cierre diferente propiedades (estas están cerradas bajo unión, concatenación, estrella de Kleene e inversión).

¿HAL está cerrado bajo inversión?

Considere el lenguaje (donde # 0 ( x ) denota el número de ceros en x ).

Es fácil decidir usando una máquina HAL: observe que la máquina necesita realizar un seguimiento de dos propiedades: el número de ceros en x vs y y la longitud de x , y (vs z ). Puede empujar a al montón por cada cero que ve en x (y luego explotar por cualquier cero visto en y ); además, empuja para cualquier bit en x , y (y luego aparece para cualquier bit de z ). Como todos los s son empujados hacia abajo en el montón, no interfieren con el conteo. El $L_{\times 2}$$x$$y$$x,y$$z$0$x$0$y$1$x,y$1$z$10$\bot$ sirve como delimitador y puede ser prácticamente ignorado.

Ahora, dejemos que , sea el lenguaje inverso. Es decir, L = { z ⊥ y ⊥ x ∣ x , y , z ∈ { 0 , 1 } , # 0 ( x ) = # 0 ( y )  y  | x | + | y | = Z } Vamos a mostrar que ninguna máquina HAL puede decidir L .$L = L_{\times 2}^R$

La intuición es lo siguiente. Como se indicó anteriormente, la máquina debe realizar un seguimiento tanto de la longitud de como del número de ceros en x , y . Sin embargo, en este caso necesita rastrearlos simultáneamente . Esto no se puede hacer a través de un montón. En más detalles, después de leer z , el montón contiene información sobre la longitud de | x | + | y | . mientras lee y, la máquina también debe mantener en el montón el número de ceros en y . Sin embargo, esta información no puede interferir con la información que el montón ya tiene sobre la longitud que esperamos $z$$x,y$$z$$|x|+|y|$$y$$y$$x$ser - estar. Muy intuitivamente, la información sobre el número de ceros estará "debajo" de la información sobre la longitud de , y luego no podremos acceder a ella mientras leemos x , o estará "encima" de esa información, haciendo que este último sea inaccesible, o el dos informaciones serán "mixtas" y carecerán de sentido.$x$$x$

Más formalmente, vamos a utilizar algún tipo de argumento de "bombeo". Es decir, tomaremos una entrada muy larga y mostraremos que el "estado" de la máquina debe repetirse durante el procesamiento de esa entrada, lo que nos permitirá "reemplazar" la entrada una vez que la máquina repita su "estado".

Para la prueba formal, requerimos una simplificación de la estructura de la máquina HAL, a saber, que no contiene un "bucle" de -transiciones 1 . Con esta suposición, podemos ver que para cada símbolo de entrada que procesa la máquina, el contenido del montón puede aumentar / disminuir a lo sumo c (para algunos constantes lo suficientemente grandes c ).$\varepsilon$$^1$$c$$c$

Prueba.
Suponga que decide L y considere una entrada lo suficientemente larga (digamos, de longitud 4 n , por lo tanto | x | = | y | = n , | z | = 2 n , ignorando los ⊥ s de aquí en adelante). Para ser concreto, arregle z , y y suponga que # 0 ( y ) = n / 2 . Observe que hay ($H$$L$$4n$$|x|=|y|=n$$|z|=2n$$\bot$$z,y$$\#_0(y) = n/2$diferentesx'S tal quez⊥y⊥x∈L.${n \choose n/2}$$x$$z\bot y \bot x \in L$

Considere el contenido del montón inmediatamente después de procesar . Contiene en la mayoría de 3 n c símbolos (donde cada símbolo es de un alfabeto fijo Γ ), por nuestra suposición. Sin embargo, hay ($z\bot y$$3nc$$\Gamma$diferentesx'sque deberían aceptarse (que es sustancialmente mayor que la cantidad de diferentes contenidos posibles para el montón, ya que esto aumenta exponencialmente, mientras que el número diferente de montones aumenta polinomialmente, ver más abajo). Tome dos entradasx1,x2que deberían aceptarse, de modo que se cumpla lo siguiente:${n \choose n/2}$$x's$$x_1,x_2$

1. El prefijo de longitud de x 1 tiene un número diferente de ceros que el prefijo de x 2 de la misma longitud.$n/2$$x_1$$x_2$
2. En el momento en la máquina lee un prefijo de longitud de la x parte, el montón se ve el mismo para ambos x 1 y x 2 , y también, la máquina está en el mismo estado (esto debe ocurrir por alguna x 1 , x 2 , para n lo suficientemente grande , ya que hay más de 2 0.8 n diferentes opciones 2 para x 1 , x 2 y como máximo ( 3.5 c n ) | Γ | |$n/2$$x$$x_1$$x_2$$x_1,x_2$$n$$2^{0.8n}$$^2$$x_1,x_2$diferentes opciones para el contenido del montón y el estado 3 ).$(3.5cn)^{|\Gamma|}|Q|$$^3$

Está claro que la máquina debe aceptar la palabra , donde x p 1 es un prefijo de x de longitud n / 2 y x s 2 es un sufijo de x 2 de la misma longitud. Tenga en cuenta que el número de ceros en x p 1 x s 2 difiere del número de ceros en x 1 y x 2 (es decir, desde # 0 ( $z\bot y \bot x_1^px_2^s$$x_1^p$$x$$n/2$$x_2^s$$x_2$$x_1^px_2^s$$x_1$$x_2$ ), debido a la forma en que elegimos x 1 y x 2 , llegamos a una contradicción.$\#_0(y)$$x_1$$x_2$

^{¿Este supuesto daña la generalidad? No lo creo, pero esto realmente requiere una prueba. Si alguien ve cómo evitar esta suposición adicional, me encantaría saberlo.} 2 ^{Arreglemos x 1 para que sea el prefijo (de longitud n / 2 tiene exactamente n / 4 ceros). Recordemos que usandola aproximación de Stirlingsabemos que log ( n}$^1$
$^2$ ^{$x_1$$n/2$$n/4$dondeH()es lafunción de entropía binaria. DesdeH(1/4)≈0,81tenemos ($\log {n \choose k} \approx nH(k/n)$$H()$$H(1/4) \approx 0.81$para lo suficientemente granden. ${n \choose n/4} > 2^{0.8n}$$n$}3^{Asumiendo el alfabetoΓ, hay| Γ| ncadenas diferentes de longitudn, así que si esto fuera una pila, estaríamos jodidos. Sin embargo, empujar "01" en un montón es equivalente a empujar "10": el montón almacena solo la versión ordenada del contenido. El número de diferentescadenasordenadasde tamañones (n+1}
$^3$ ^{$\Gamma$$|\Gamma|^n$$n$$n$, para una constante| Γ| .${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$$|\Gamma|$}