En la descripción formal de los Autómatas de empuje determinista, permiten movimientos , donde la máquina puede hacer estallar o empujar símbolos en la pila sin leer un símbolo de la entrada. Si estos movimientos no están permitidos, y la pila solo se puede modificar una vez después de cada símbolo leído, ¿son los autómatas resultantes iguales a la potencia de los DPDA?ϵ
Puede haber algo trivial que me falta con respecto al uso del conjunto de potencia de como su nuevo , lo que le permite "comprimir" mueve al autómata equivalente sin ellos, similar a cómo puede comprimir movimientos de en un DFA Simplemente parece que tal conversión no es tan trivial como para los DFA, y no estoy seguro de que sea posible.Γ ϵ ϵ
Entonces, ¿son los dos equivalentes en el poder? Solo pregunto porque todo el mundo parece asumir que los DPDA tienen movimientos y me pregunto por qué existe esa suposición, ya que parece un modelo más complejo.
fuente
Respuestas:
Quizás encontré información relevante en:
Jean-Michel Autebert, Jean Berstel, Luc Boasson; Lenguajes sin contexto y autómatas pushdown; Manual de idiomas formales; 1997, pp 111-174
Los DPDA sin transiciones se conocen como autómatas deterministas en tiempo real .ϵ
Son menos potentes que los DPDA, por ejemplo
es determinista y puede ser reconocido por un DPDA, pero no puede ser reconocido por ningún DPDA en tiempo real .
Lo que puede hacer es eliminar el aumento de -transitions:ϵ
Proposición 5.4 : Para cualquier DPDA es posible construir un DPDA que reconozca el mismo lenguaje de manera que cualquier -rule esté disminuyendo.ϵ
fuente