¿Hay variantes de autómatas visiblemente pushdown que permiten empujar palabras en la pila?

Me pregunto, ¿hay algún trabajo o investigación que trate con autómatas visiblemente pushdown, pero que permita que las palabras, en lugar de letras simples, sean empujadas a la pila.

Alternativamente, una construcción que permita que los símbolos se presionen en las transiciones $\epsilon$ podría lograr el mismo objetivo.

Obviamente, tales variaciones se pueden formar, pero me pregunto si arruina las propiedades de cierre y capacidad de decisión que hacen que los VPA sean interesantes.

Estoy mirando una construcción en la que utilizo la pila como contador, incrementándola en constantes en función de los símbolos iniciales leídos, y luego en cuenta regresiva en función de otros símbolos leídos.

Para cualquiera que no sepa, los autómatas visiblemente pushdown son aquellos en los que el alfabeto se puede dividir en símbolos de empuje, símbolos emergentes y símbolos que no afectan en absoluto a la pila. La elección de empujar versus reventar está completamente determinada por el símbolo actual que se lee. Están cerrados bajo intersección, unión, concatenación, estrella y complemento, dándoles una gran cantidad de propiedades decidibles. Vea este documento para más información.

reference-request fl.formal-languages automata-theory context-free context-free-languages jmite
fuente

Parece que la pregunta obvia es si tales autómatas son equivalentes a los autómatas estándar pushdown con las "palabras" convertidas en secuencias de estados. afaik, si? de lo contrario, sería útil un ejemplo ilustrativo de un caso en el que falla.

vzn

@vzn No pueden ser equivalentes. Esas PDAs visiblemente parecen ser estrictamente más débiles. La última vez que revisé, las CFL no estaban cerradas bajo la intersección.

Kai

Por lo tanto, VPDAs son cerrados bajo intersección, y son conocidos por ser correctamente entre

. Sin embargo, no tengo idea si mi variante está cerrada debajo de la intersección, por lo que podría ser equivalente. Dudo que lo sea, pero no estoy seguro.

R E G

$REG$

D C F L

$DCFL$

jmite

Este documento dx.doi.org/10.1145/1516512.1516518 ofrece una caracterización gramatical de los VPDA y una construcción para la conversión entre las gramáticas y los VPDA. ¿Posiblemente la gramática se puede usar para simular empujar palabras enteras?

Evgenij Thorstensen

¿Por qué empujar una palabra sobre un símbolo sería equivalente a permitir empujar en transiciones eps?

domotorp

Respuestas:

Con empujes epsilon

Para la versión con avances en las transiciones épsilon, la prueba de indecidibilidad de la universalidad de los autómatas pushdown puede adaptarse a esta nueva configuración, por lo que perdemos al menos las siguientes propiedades: cierre bajo complementación, determinabilidad, capacidad de decisión de universalidad e inclusión.

Esquema de prueba: tome una máquina de Turing , queremos construir un VPA con epsilon-push de tal manera que sea universal si y solo si M no acepta la ejecución. $M$ $A$

Diseñamos modo que una palabra no sea aceptada si y solo tiene la forma: $A$

donde

# C_{0} & C_{0} $ (\bar{C_{0}})^{R} # C_{1} & C_{1} $ (\bar{C_{1}})^{R} # C_{2} & C_{2} $ (\bar{C_{2}})^{R} \dots # C_{n} & C_{n} $ (\bar{C_{n}})^{R}

$\#C_0\&C_0\$(\overline{C_0})^R\#C_1\&C_1\$(\overline{C_1})^R\#C_2\&C_2\$(\overline{C_2})^R\dots\#C_n\&C_n\$(\overline{C_n})^R$

Cada codifica una configuración válida de $C_i$ $M$
es inicial, está aceptando $C_0$ $C_n$
es el reverso de una palabra $u^R$ $u$
es una copia deusando letras pop $\overline{u}$ $u$
son símbolos de separación especiales que no están en el alfabeto de $\#,\&,\$$ $M$
es siempre una transición válida de $C_i\to C_{i+1}$ $M$

El VPA se ve obligado a hacer pop en factores de la forma . puede determinar de manera no determinista una violación de cualquiera de las propiedades y verificarla. La clave es que puede presionar o no hacer nada, lo que permite verificar todas las condiciones (en realidad, adivinar sus violaciones). En particular, puede adivinar que la primera (o segunda) aparición de no coincide , ignorando el otro componente. También puede adivinar que $A$ $C_i^R$ $A$ $C_i$ $C_i$ $(\overline{C_i})^R$ $C_i\to C_{i+1}$ no es una transición válida, presionando ambas ocurrencias de , luego haciendo estallar una, no presione y compare con el contenido de la pila. Por otro que no son parte de la adivinanzas, uno de los componentes se empuja y la se extrae. $C_i$ $C_{i+1}$ $(\overline{C_{i+1}})^R$ $C_j$ $(\overline{C_j})^R$

Empujando palabras

$(S,R,u)$ $u\in A^*$ $a$ $(S,R,va)$ $(S',R',v)$ $S'$ $R'$

Denis
fuente