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

8

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 estado: los autómatas de min-montón. Pudieron demostrar que el conjunto de idiomas aceptados por tales máquinas (HUNAL) 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.

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 complementación?

Patrick87
fuente

Respuestas:

4

Reclamo :HUNALNo está cerrado contra el complemento.

Idea de prueba : hemos acordado quemiPAGSUNAL (el lenguaje de incluso palíndromos sobre un alfabeto no unario) no está en HUNAL. Mostramos quemiPAGSUNAL¯HUNAL.
Esto funciona solo para el tipo 1 (ya que el tipo 2 puede aceptarmiPAGSUNAL); Sin embargo, la prueba se puede adaptar para adaptarse al tipo 2, ver más abajo.

Prueba : tenga en cuenta que

miPAGSUNAL¯={vw:El |vEl |=El |wEl |,vwR} {w:El |wEl |2norte+1}

Construimos un autómata de montón mínimo con dos símbolos de montón si<una que funciona así:

  • En el estado inicial, decida sin determinar si la longitud de la entrada es par.
  • En el camino desigual, use el control finito para aceptar la entrada si y solo si su longitud es impar.
  • En el camino uniforme, proceda así:
    v1 ... vyo+una vyo+1 ... vnorte+si wnorte ... wyo+1-si wyo ... w1-una
    • Comience agregando uno una para acumular cada símbolo de lectura.
    • En una posición determinada no determinista, almacene el símbolo actual en control finito y comience a agregar uno. si (y no una) para acumular cada símbolo de lectura.
    • En una posición determinada no determinista, deje de agregar símbolos y consuma uno si por símbolo de entrada.
    • Cuando todo sise consumen, compare el símbolo actual con el que está almacenado en el control. Si son desiguales, continúe; De lo contrario, rechazar la entrada.
    • Consume uno unapor símbolo de entrada. Si el montón está vacío al mismo tiempo que termina la entrada, acepte la palabra; rechazar lo contrario.

El autómata de montón mínimo descrito acepta miPAGSUNAL¯. Como complemento,miPAGSUNAL, no está enHUNAL, hemos probado el reclamo.

Nota: La prueba se puede realizar de la misma manera con{www{una,si}}(que está enCSLHUNAL) y su complemento. Esto extiende el resultado anterior al tipo 2.

Rafael
fuente
+1 Muy buena respuesta, para los autómatas min-heap de tipo 1 (definición original). Con esto, dado el argumento relativamente simple que creo que muestra que los idiomas aceptados por los autómatas de tipo 1 min-heap están cerrados wrt union, también sabemos que el conjunto de idiomas aceptados por los autómatas de tipo-1 min-heap no está cerrado bajo intersección o diferencia, de argumentos igualmente simples. Le daré a esto un día más o menos y luego aceptaré, solo para darles a otras personas la oportunidad de visitar y, posiblemente, proporcionar otras respuestas ... Además, ¿qué pasa con los autómatas de tipo 2 min-montón (es decir, la versión más natural que usted sugirió)?
Patrick87
Wow, hombre, eres un tipo genial.
Patrick87